heaps_running_median.py 文件源码

def rebalance_heaps():
    """Ensures that no element in the upper half is less than any element in the lower half."""
    if not (len(lower_half_max_heap) >= 1 and len(upper_half_min_heap) >= 1):
        return  # Don't need to rebalance if one of them is empty.

    max_from_lower_half = lower_half_max_heap[0] * -1
    min_from_upper_half = upper_half_min_heap[0]

    if min_from_upper_half < max_from_lower_half:
        # Upper half has smaller elements than that of lower half.
        while min_from_upper_half < max_from_lower_half:
            # Swap elements.
            max_from_lower_half = heapq.heappop(lower_half_max_heap) * -1
            min_from_upper_half = heapq.heappop(upper_half_min_heap)
            heapq.heappush(lower_half_max_heap, min_from_upper_half * -1)
            heapq.heappush(upper_half_min_heap, max_from_lower_half)
            # heapq will handle restructuring heap so smallest values will be at index 0.
            max_from_lower_half = lower_half_max_heap[0] * -1
            min_from_upper_half = upper_half_min_heap[0]