Skip to main content

The Binary Heap as an Implicit Tree

What This Concept Is​

A binary min-heap uses a complete binary tree stored in an array. For zero-based index i, children are 2i+1 and 2i+2 when present; the parent of a nonroot is (i-1)//2. Every parent is no greater than its children. This local invariant implies that the root is a minimum, but says nothing about ordering siblings.

Push appends then sifts up. Pop saves the root, replaces it with the last record, and sifts down through the smaller child. Each sift follows a path of O(log n) edges. Peek reads the root in O(1).

Why It Matters Here​

A heap solves repeated minimum extraction without maintaining complete sorted order. The array representation avoids per-node links, but it still allocates storage and its root-to-leaf accesses are not perfectly sequential. Runtime locality and allocation costs remain engineering questions.

Concrete Examples​

Bottom-up heapify [5,1,1,3]. The last internal node is index 1; its child 3 already satisfies order. At root 5, choose a child with value 1 and swap; if that path reaches child 3, continue. One valid result is [1,3,1,5]. Draining returns [1,1,3,5], although the heap array itself is not sorted.

Heapify sifts internal nodes from last to first, so both child subtrees are heaps when a parent is repaired. Its cost is linear: the total possible downward steps are bounded by the sum over h>=1 of the number of nodes of height at least h. That count is at most floor(n/2^h), and the sum is less than n. Constant work per level plus loop overhead yields O(n), with Omega(n) work to process the input.

Common Confusion / Misconceptions​

n calls each bounded by O(log n) give a valid but loose O(n log n) construction bound. Most nodes have little or no distance to travel. In contrast, building by repeated pushes can take Theta(n log n) sift work. A heap is not a search tree: arbitrary-key lookup can require visiting every node. Duplicate values do not imply FIFO order. Dynamic-array push may occasionally pay O(n) reallocation although sift work is logarithmic.

How To Use It​

State the comparator and empty-heap behavior. Pick the better child before swapping downward, handle a lone left child, and stop once local order holds. In Lab D, constructor input must remain unchanged. Compare mixed operations to a list oracle and separately inspect the implementation for bottom-up heapify.

Check Yourself​

  1. Why are both child subtrees already heaps during bottom-up construction?
  2. What breaks if sift-down always chooses the left child?
  3. How does the height sum avoid the loose n log n bound?
  4. Why is sorted draining insufficient to prove linear heapify?

Mini Drill or Application​

Trace heapify on seven descending keys. Record swaps and active subtree roots. Prove the invariant after each parent is processed. Then test a two-element heap, equal keys, repeated empty operations, and interleaved push/pop. See P12.

Read This Only If Stuck​

Use CLRS, Skiena, or Sedgewick and Wayne for binary heap invariants, sift operations, and linear-time heap construction. These links open book indexes; find the named topic in your edition. Use the reading guide for the bounded assignment and worked examples before adding another source.