Heap-Backed Priority Queue

Foundations

A binary heap is a complete binary tree stored in a plain list: every level is full except possibly the last, which fills from the left. With no gaps, the level-order list from Trees becomes exact index arithmetic: the children of index i sit at 2i + 1 and 2i + 2, and its parent at (i - 1) // 2. No pointers are needed; the index arithmetic is the tree.

A min-heap adds one rule: every parent is at most its children, so the smallest item is always at index 0. Pushing appends the item at the end and swaps it up while it is smaller than its parent; popping moves the last item to the root and swaps it down past its smaller child. Each repair walks one root-to-leaf path, O(log n) steps, and reading the top is O(1).

Python's heapq.heapify turns nums = [7, 1, 5, 3, 6] into the min-heap [1, 3, 5, 7, 6] in place: 1 is at index 0, its children 3 and 5 at indexes 1 and 2, and 3's children 7 and 6 at 3 and 4. Popping returns 1; then 6 moves to the root and sinks past 3, leaving [3, 6, 5, 7]. For a max-heap, store negated values in the same min-heap.

• Depth-First Tree Traversal

  A heap is a binary tree with a stronger shape rule. That lesson covers parents, children, and the level-order list.

  Open lesson

Case Scenario

Last Stone Weight repeatedly needs the two heaviest stones: smash them, and if their weights differ, put the difference back. That is a max-heap, which heapq gets by storing each weight as its negative, so the heaviest stone is the smallest number, on top. For stones = [2, 7, 4, 1, 8, 1], the rounds smash 8 with 7, 4 with 2, 2 with 1, and 1 with 1, leaving 1.

The direct approach sorts the stones every round, smashes the two largest, and puts the result back. Each sort costs O(n log n), and there can be n rounds, so the work is O(n² log n), nearly all of it spent reordering stones that are not yet among the two heaviest.