Drag across the board. Click it, then use ← → to step and Space to play.
A heap is a complete binary tree (the structure property: every level full, the last one filled left to right) where every parent is smaller than its children (the order property, for a min heap). So the minimum is always at the top. Because the tree is complete, it needs no pointers: it is just a list, with the children of index i at 2i + 1 and 2i + 2. A new value bubbles up; after a pop, the replacement sinks down like a stone. Both travel one path, so both are O(log n). Python's heapq is a min heap; for a max heap, negate values going in and coming out.
FIG. 8 · The same heap drawn twice: as a tree on the board, and as the list it really is, in the channel underneath. Dotted circles are the free slots the tree will fill next, left to right. Small numbers beside each node are its list index. Red is the value being moved; the red-ringed node is the one it is compared with. Callouts: A root (the min), B last level, C levels.
def heapify(a): # what heapq.heapify does, O(n)
for i in range(len(a) // 2 - 1, -1, -1):
sift_down(a, i) # leaves are already heaps
def sift_down(a, i):
while 2 * i + 1 < len(a):
c = 2 * i + 1 # left child
if c + 1 < len(a) and a[c + 1] < a[c]:
c += 1 # right child is smaller
if a[i] <= a[c]:
break # parent already smaller: done
a[i], a[c] = a[c], a[i] # sink down
i = c
def heappush(a, x): # O(log n)
a.append(x) # structure: next free slot
i = len(a) - 1
while i > 0:
p = (i - 1) // 2 # parent
if a[p] <= a[i]:
break # order property holds
a[i], a[p] = a[p], a[i] # bubble up
i = p
def heappop(a): # O(log n)
top = a[0] # smallest; peeking is O(1)
last = a.pop() # take the last leaf
if a:
a[0] = last # move it to the root
sift_down(a, 0) # sink it into place
return top
def sift_down(a, i):
while 2 * i + 1 < len(a):
c = 2 * i + 1 # left child
if c + 1 < len(a) and a[c + 1] < a[c]:
c += 1 # right child is smaller
if a[i] <= a[c]:
break # parent already smaller: done
a[i], a[c] = a[c], a[i] # sink down
i = c
heap = []
for x in [5, 3, 8]:
heapq.heappush(heap, -x) # max heap: negate going in
largest = -heapq.heappop(heap) # and coming out: 8
def k_largest(nums, k): # min heap of size k
heap = []
for x in nums:
heapq.heappush(heap, x)
if len(heap) > k:
heapq.heappop(heap) # drop the smallest
return heap # heap[0] is the kth largest
def lastStoneWeight(stones): # LeetCode 1046
heap = [-s for s in stones] # max heap: negate
heapq.heapify(heap)
while len(heap) > 1:
y = -heapq.heappop(heap) # heaviest
x = -heapq.heappop(heap) # second heaviest
if x != y:
heapq.heappush(heap, -(y - x))
return -heap[0] if heap else 0
nums = [3, 2, 1, 5, 6, 4], k = 2. Keep a min heap of the k biggest seen so far; whenever it grows past k, pop the smallest. The root is the answer: 5. Trigger: "kth largest", "top k".
stones = [2, 7, 4, 1, 8, 1]. Each round smash the two heaviest; if they differ, the difference goes back. A max heap (negated) hands out the heaviest every time. Answer: 1. Trigger: "always take the largest next".
The last column fills in when a run finishes.
| Operation | Time | Why | Last run on the bench |
|---|---|---|---|
| Peek (heap[0]) | O(1) | The minimum is always at index 0. | — |
| heappush | O(log n) | Append, then bubble up one path: at most one swap per level, and a complete tree has about log₂ n levels. | not run yet |
| heappop | O(log n) | Move the last leaf to the root, then sink it down one path. | not run yet |
| heapify | O(n) | Half the nodes are leaves and never move; a quarter sink at most one level, an eighth two… The total is under 2n swaps. | not run yet |
| Top k / kth largest (size-k heap) | O(n log k) | n pushes and pops on a heap of size k. Space O(k). | not run yet |
A BST (page 6) orders left < node < right, so it can search for any value. A heap only promises parent < children, nothing about left vs right. That is less order, which is why it is cheaper to keep (no balancing, no pointers) and why it can only answer one question fast: what is the smallest?
Keep a heap of size k: a min heap for the k largest, a max heap (negated) for the k smallest.
Repeatedly removing the min or max while new items keep arriving: a priority queue.
import heapq
nums = [5, 3, 8, 1]
heapq.heapify(nums) # list -> min heap, in place, O(n)
print(nums[0]) # peek smallest: 1, O(1)
heapq.heappush(nums, 2) # add, O(log n)
print(heapq.heappop(nums)) # remove smallest: 1, O(log n)
print(heapq.heappop(nums)) # next smallest: 2
# Max heap: negate in, negate out
max_heap = []
for x in [5, 3, 8]:
heapq.heappush(max_heap, -x)
print(-heapq.heappop(max_heap)) # largest: 8
# Top k
print(heapq.nlargest(2, [5, 3, 8, 1])) # [8, 5]
def k_largest(nums, k): # min heap of size k
heap = []
for x in nums:
heapq.heappush(heap, x)
if len(heap) > k:
heapq.heappop(heap) # drop the smallest
return heap # heap[0] is the kth largest