Heap invariant and array representation

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

A min-heap's parent is no greater than its children. In zero-based storage, children are 2i+1 and 2i+2; parent is (i-1)//2 for i>0. The root is globally smallest.

Work through an example

[1,3,2,8,5] is a valid min-heap despite 3 preceding 2. The array is not fully sorted; only parent-child relationships are constrained.

Time and space complexity

Peek O(1); arbitrary search O(n); heap storage O(n).

Why it works

Every root-to-leaf path is nondecreasing in a min-heap.

Common mistakes

Heap order does not mean sorted siblings.
Child indices may exceed length.

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.