Combining two heaps

What is a heap?

A heap is a tree-shaped structure used to repeatedly get the item with the highest priority. In a min-heap, every parent is no larger than its children, so the smallest item is at the root. A priority queue uses this rule to return the most urgent item rather than the earliest item added.

Example: For values 8, 2, and 5, a min-heap places 2 at the root. Removing 2 rearranges the remaining values so that 5 becomes the smallest available item. The rest of a heap is not fully sorted.

Helpful before this chapter

If these ideas are new, begin with:

Arrays and dynamic arrays Binary trees

Understand the idea

Streaming median splits values into lower and upper halves. A max-heap gives the largest lower value; a min-heap gives the smallest upper value. Maintain order and sizes after every insertion.

Work through an example

After 3,1,5,2, lower contains 1,2 and upper 3,5; median=(2+3)/2=2.5. Negating values implements a max-heap with classic heapq operations.

Time and space complexity

O(log n) insertion/O(1) median/O(n) stored stream values.

Why it works

Every lower value≤every upper value; lower has equal size or one extra element.

Common mistakes

Balance sizes without violating ordering.
Empty median needs a defined error.

Chapter lab · Python implementation

A heap gives fast access to one extreme, without sorting all stored values. Python heapq is a min-heap API. Our lab keeps the largest k stream elements in a size-k min-heap; the root is the smallest retained candidate and therefore the kth-largest seen value.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

import heapq

def top_k(values,k):
    if k<0: raise ValueError('k must be nonnegative')
    if k==0: return []
    heap=[]
    for x in values:
        if len(heap)<k: heapq.heappush(heap,x)
        elif x>heap[0]: heapq.heapreplace(heap,x)
    return sorted(heap,reverse=True)

class Median:
    def __init__(self): self.low,self.high=[],[]
    def add(self,x):
        heapq.heappush(self.low,-x)
        heapq.heappush(self.high,-heapq.heappop(self.low))
        if len(self.high)>len(self.low):
            heapq.heappush(self.low,-heapq.heappop(self.high))
    def value(self):
        if not self.low: raise ValueError('empty stream')
        if len(self.low)>len(self.high): return -self.low[0]
        return (-self.low[0]+self.high[0])/2

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

assert top_k([3,1,5,2,4],2)==[5,4]
assert top_k([1],0)==[] and top_k([1],3)==[1]
m=Median()
for x in [3,1,5,2]: m.add(x)
assert m.value()==2.5
m.add(4); assert m.value()==3

CHECK YOUR UNDERSTANDING

What is a heap?

Keep the first two values.