Heaps

Problem

You process items in priority order, but the set of items changes as you go: new tasks arrive, a finished task produces a new one, or a simulation needs "the earliest free machine" over and over. Sorting once does not help because the order changes; sorting again after each change costs O(n log n) per step. Scanning for the minimum costs O(n) per step. A binary heap does both operations, insert and take-the-best, in O(log n). Python ships one as the heapq module, which is a min-heap stored in a plain list.

Intuition

Picture a tournament bracket where the winner is always the smallest number. The winner sits at the top; below it are the winners of each half; and so on down. You do not know the exact order of the losers, but you know each parent beats its children. To add a new item you put it at the bottom and let it climb past any parent it beats. To remove the winner you take the top, put the last item in its place, and let it sink until it fits. Climbing and sinking each touch one item per level, and a tree of n items has only about log₂ n levels, which is why both are O(log n).

The trick that makes this fast in practice is that the tree needs no pointers. Store it as a list in level order: the children of the item at index i sit at 2i + 1 and 2i + 2, and its parent sits at (i - 1) // 2. The shape is always "full on every level but the last, filled from the left", so the list has no gaps.

The same heap twice: as a tree and as the list that stores it, with the index under each box. Amber is the minimum, always at index 0. The diagram scrolls sideways on a narrow screen.

Mechanics

The invariant

Two rules hold at all times. Shape: the tree is complete, meaning every level is full except possibly the last, which fills from the left; this is what lets a list store it. Order: every item is less than or equal to its children (for a min-heap). The order rule only relates parent and child, so siblings and cousins are in no particular order. That is the "partial order" a heap keeps and a sorted array does not need to.

Push and pop

Push appends the item at the end of the list, which keeps the shape, and then sifts up: while the item is smaller than its parent, swap them. Only the order along one root-to-leaf path can be wrong, and sifting repairs exactly that path. Pop removes the root, which is the minimum. To keep the shape, it moves the last item into the root, then sifts down: swap with the smaller child while that child is smaller than the item. At every step the item is the smallest of itself and its two children after the swap, so the order rule is restored below it. Each loop moves one level, so each operation is O(log n).

Building a heap from n items

Pushing n items one at a time costs O(n log n). Better: put all items in the list as they are and sift down every non-leaf, from the last parent back to the root. Half of the items are leaves and need no work, a quarter sift at most one level, an eighth at most two, and so on, so the total is the sum n/2 · 0 + n/4 · 1 + n/8 · 2 + …, which is O(n). That is what heapq.heapify does.

Counting swaps for the same 9 values. The gap grows with n: heapify is linear, pushing is n log n.

Worked example

Pushing. Push 7, 3, 9, 1, 5, 2 into an empty min-heap. Each row shows the list after the push and how many swaps the climb needed.

Pushing 1 starts at index 3 under 7, and climbs 2 levels past 7 and then 3 to the root, because it is smaller than everything above it.

Popping. The heap is 1, 3, 2, 7, 5, 9. Pop returns 1; the last item, 9, moves to the root and sinks, using 1 swap, and the list becomes 2, 3, 9, 7, 5.

A simulation. Smash the two heaviest stones from 2, 7, 4, 1, 8, 1: the lighter is gone and the difference, if any, goes back.

After 4 rounds the last stone weighs 1.

After the pop: amber is the new minimum and green is the value that was moved from the end and sank.

Implementation

import heapq


heap = []
heapq.heappush(heap, 5)          # O(log n)
smallest = heapq.heappop(heap)   # O(log n)
peek = heap[0] if heap else None # O(1), never heap[-1]

items = [7, 3, 9, 1, 5, 2]
heapq.heapify(items)             # O(n), in place

# Max-heap: negate on the way in, negate back on the way out.
def last_stone_weight(stones):
    heap = [-s for s in stones]
    heapq.heapify(heap)
    while len(heap) > 1:
        first = -heapq.heappop(heap)
        second = -heapq.heappop(heap)
        if first != second:
            heapq.heappush(heap, -(first - second))
    return -heap[0] if heap else 0


# Priority by a key: push tuples; ties compare the next field.
def single_threaded_cpu(tasks):
    order = sorted((enqueue, duration, i) for i, (enqueue, duration) in enumerate(tasks))
    ready, result, now, i = [], [], 0, 0
    while i < len(order) or ready:
        if not ready and now < order[i][0]:
            now = order[i][0]                      # idle: jump to the next arrival
        while i < len(order) and order[i][0] <= now:
            enqueue, duration, index = order[i]
            heapq.heappush(ready, (duration, index))
            i += 1
        duration, index = heapq.heappop(ready)
        now += duration
        result.append(index)
    return result


# Earliest free resource: a heap of finish times.
def min_rooms(intervals):
    ends = []
    for start, end in sorted(intervals):
        if ends and ends[0] <= start:
            heapq.heapreplace(ends, end)           # reuse the room that freed up
        else:
            heapq.heappush(ends, end)
    return len(ends)

heapq has no peek method and no max-heap; heap[0] is the minimum, and negation turns it into a max-heap. heapreplace pops then pushes in one step and is faster than doing the two separately.

Variations and edge cases

• Tuples as priorities. (priority, tiebreak, payload) compares field by field. If two entries tie on every field before the payload, Python compares the payloads and may raise a TypeError for objects that cannot be ordered, so include a unique counter or index as the tiebreak.
• Lazy deletion. A binary heap cannot cheaply remove an arbitrary item. Mark it dead in a set and discard it when it reaches the top. The heap can then hold stale entries, so count live items separately.
• Two heaps. A max-heap for the lower half and a min-heap for the upper half expose the median; a later page covers it.
• Heap of lists or streams. Push (value, stream, position) to merge sorted inputs.
• Edge cases: an empty heap (heappop raises IndexError, so check first), a single element, duplicates, and values that are floats or negative numbers when negating for a max-heap. Time arithmetic in simulations needs a rule for idle gaps, as in the CPU example.

Complexity and tradeoffs

• Time: push and pop are O(log n); peek is O(1); heapify is O(n). A simulation that does n pushes and n pops is O(n log n).
• Space: O(n) for the list; sifting is in place, so no extra memory.
• Baseline. A plain list scanned with min costs O(n) per extraction, O(n²) for a run of n; a sorted list costs O(n) per insertion. A heap balances the two at O(log n) each.
• When it fails. If every item is known up front and you only need them in order, sorting is simpler and has a smaller constant. If you need search by value, updates to priorities, or removal from the middle, a balanced search tree or an indexed heap fits better. A heap cannot list its contents in order without popping every item.

Problems

The home problems are all simulations: take the best item, act on it, and put new items back. Many other problems use a heap as a supporting tool, and they appear in "also uses" below, each taught on a page where the heap is only one part of the idea.

Easy

• 1046. Last Stone Weight NeetCode 150 NeetCode 250
  A max-heap always gives the two heaviest stones; push back their difference until at most one stone remains.

Medium

• 1834. Single-Threaded CPU NeetCode 250
  Sort tasks by arrival time and, whenever the CPU is free, pick the shortest available task from a heap.

Hard

• 2402. Meeting Rooms III NeetCode 250
  Use two heaps, free rooms by number and busy rooms by end time, and delay a meeting to the earliest end when no room is free.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 703. Kth Largest Element in a Stream Easy
• 215. Kth Largest Element in an Array Medium
• 253. Meeting Rooms II Medium
• 355. Design Twitter Medium
• 621. Task Scheduler Medium
• 692. Top K Frequent Words Medium
• 743. Network Delay Time Medium
• 767. Reorganize String Medium
• 912. Sort an Array Medium
• 973. K Closest Points to Origin Medium
• 1405. Longest Happy String Medium
• 1584. Min Cost to Connect All Points Medium
• 23. Merge k Sorted Lists Hard
• 295. Find Median from Data Stream Hard
• 502. IPO Hard
• 1851. Minimum Interval to Include Each Query Hard

Connections

The heap is a tree stored in an array, so it connects the tree pages to the toolkit page that introduced heapq. The next pages specialise it: keeping a heap of fixed size k, merging k sorted streams, and splitting data across two heaps for a running median. Dijkstra's shortest paths later reuse the same push-and-pop loop with distances as priorities, and sorting by repeatedly popping is heapsort.

Check yourself

References

• Williams, "Algorithm 232: Heapsort", Communications of the ACM 7(6), 1964: the binary heap.
• Floyd, "Algorithm 245: Treesort 3", Communications of the ACM 7(12), 1964: the linear-time bottom-up build.
• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, chapter 6: heapsort and priority queues.
• Sedgewick and Wayne, Algorithms, section 2.4: priority queues.
• Skiena, The Algorithm Design Manual, the section on priority queues.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.