Heap Basics

The Idea

A heap is a complete binary tree where every parent beats its children — smaller, in a min-heap. That is a much weaker promise than sorting, and much cheaper to keep.

Only the root is guaranteed. Push and pop cost O(log n); peeking at the winner costs O(1). The tree lives in a plain array: node i has children at 2i + 1 and 2i + 2.

Real-World Example

An auction house's bid board only ever shows the current highest offer. Nobody maintains a full ranking of every bid ever shouted — that work would be wasted, because only the top one can win. A new bid either takes the board or quietly disappears into the pile.

The Code

import heapq

bids = [7, 3, 9, 1]
heapq.heapify(bids)            # rearranges in place, O(n)
print(bids[0])                 # 1  -> the winner, read in O(1)
heapq.heappush(bids, 2)        # O(log n)
print(heapq.heappop(bids))     # 1  -> removes the minimum
print(heapq.heappop(bids))     # 2

# Python has no max-heap: negate on the way in and out.
top = []
for x in [7, 3, 9]:
    heapq.heappush(top, -x)
print(-top[0])                 # 9

import heapq
h = [5, 8, 2]
heapq.heapify(h)
heapq.heappush(h, 4)
print(heapq.heappop(h), heapq.heappop(h))