How Does a Binary Heap Support O(1) Min and O(log n) Extract?

A binary heap is a complete binary tree data structure that satisfies the heap-order property, allowing a priority queue to inspect its smallest element in constant time and remove it in logarithmic time. By storing the tree in a contiguous array and maintaining a partial order between parent and child nodes, the minimum value always sits at the root while structural updates remain bounded by the height of the tree.

Structure and the Heap-Order Property

A min-binary heap is a binary tree that obeys two invariants:

  1. Shape property: The tree is complete, meaning every level is completely filled except possibly the last, which is filled from left to right.
  2. Heap-order property: For every node \(i\) other than the root, the key of its parent is less than or equal to the key of \(i\): \[\text{key}(\text{parent}(i)) \le \text{key}(i)\]

Because the tree is complete, it can be stored compactly in a zero-indexed array \(A\) of length \(n\) without explicit pointers. For any node at index \(i\):

  • Its left child is at index \(2i + 1\).
  • Its right child is at index \(2i + 2\).
  • Its parent is at index \(\lfloor (i - 1) / 2 \rfloor\).

Why Minimum Inspection Takes \(O(1)\) Time

By induction on the heap-order property, no node in the tree can have a smaller key than its parent, and therefore no node can have a smaller key than the root. As a result, the minimum element is always located at index \(0\) of the underlying array \(A[0]\).

Inspecting the minimum element—often called peek or find-min—simply reads and returns \(A[0]\). Because array indexing takes constant time and no tree traversal or restructuring is required, minimum inspection runs in \(O(1)\) time.

Why Extraction Takes \(O(\log n)\) Time

Removing the minimum element—often called extract-min—must both return \(A[0]\) and restore the shape and heap-order invariants for the remaining \(n - 1\) elements. This is done in three steps:

  1. Save the root: Store \(A[0]\) to return at the end.
  2. Replace and shrink: Move the last element \(A[n - 1]\) into \(A[0]\) and decrement the heap size \(n\) by \(1\). Moving the last element preserves the complete-tree shape property.
  3. Sift down (heapify-down): The new root may violate the heap-order property. Compare it with its smaller child; if the root is larger, swap them and repeat the process downward until the node is smaller than both of its children or becomes a leaf.

Because a complete binary tree with \(n\) nodes has height \(h = \lfloor \log_2 n \rfloor\), any root-to-leaf path has at most \(h + 1\) nodes. Each step of the sift-down procedure performs at most two comparisons (to find the smaller child and compare it with the current node) and one swap, advancing one level deeper in the tree. Therefore, the total work for extract-min is bounded by \(O(\log n)\) in the worst case.