Previous Topic

What Is a Heap?

A heap is a specialized tree-based data structure that maintains a strong ordering property on its elements: every node is ordered relative to its children. In a min-heap, each node is less than or equal to its children, so the minimum element is always at the root; in a max-heap, the root holds the maximum. Heaps provide fast retrieval of the extreme (min or max) without fully sorting all elements.

Heap Property

• Min-heap: key(parent) ≤ key(children)
• Max-heap: key(parent) ≥ key(children)
• The structure is typically a complete binary tree: all levels filled except possibly the last, which is filled left to right.

Because the tree is complete, heaps are compact and map neatly onto arrays.

Array Representation

Binary heaps are most often stored in arrays for cache efficiency and simplicity. Given a node at index i:

• For 0-based indexing: left = 2i + 1, right = 2i + 2, parent = floor((i - 1) / 2)
• For 1-based indexing: left = 2i, right = 2i + 1, parent = floor(i / 2)

No explicit pointers are needed; the complete-tree shape is implied by the array length.

Core Operations and Complexity

• Peek (min/max): O(1)
• Insert (push): O(log n) via sift-up
• Extract-min/max (pop): O(log n) via swap-root-with-last + sift-down
• Decrease-key/Increase-key: O(log n) (requires a handle or index to the element)
• Build-heap from n items: O(n) using bottom-up heapify

Heapify and Build-Heap

Bottom-up heap construction starts from the last non-leaf and calls sift-down on each node in reverse level order. Despite each sift-down costing up to O(log n), the total work sums to O(n) because lower levels are cheaper and more numerous.

function heapify(A):
  n = length(A)
  for i from parent(n-1) down to 0:
    siftDown(A, i, n)

function siftDown(A, i, n):
  while true:
    left = 2*i + 1; right = 2*i + 2
    smallest = i
    if left < n and A[left] < A[smallest]: smallest = left
    if right < n and A[right] < A[smallest]: smallest = right
    if smallest == i: break
    swap A[i], A[smallest]
    i = smallest

Heapsort

Heapsort uses a heap to sort in-place:

• Build a max-heap.
• Repeat: swap root with the last element, shrink the heap size, sift-down from the root.

Time complexity is O(n log n), extra space is O(1), and it is not stable (equal elements may change relative order).

Applications

• Priority queues: schedule tasks by priority or time, serve the highest/lowest priority first.
• Graph algorithms: Dijkstra’s and Prim’s use min-heaps for selecting the next closest vertex/edge.
• Top-k problems: maintain a bounded heap to track the k smallest/largest items.
• Streaming median: two-heaps method (max-heap for lower half, min-heap for upper half).
• Event simulation: process future events in time order with a min-heap.
• Load balancing and scheduling: pick next job, earliest deadline, or smallest remaining time.

Variants and Trade-offs

• Binary heap: simple, fast in practice; O(log n) updates, O(1) peek.
• D-ary heap: larger branching factor; shallower tree, fewer comparisons per level; useful when decrease-key is frequent.
• Binomial heap: supports efficient meld (union of heaps) in O(log n).
• Fibonacci heap: amortized O(1) decrease-key and insert; O(log n) extract-min; useful in theoretical bounds for graph algorithms.
• Pairing/Leftist/Skew heaps: simpler meldable heaps with good practical performance.

Implementation Tips

• Indexing: be consistent about 0-based vs 1-based; adjust parent/child formulas accordingly.
• Comparators: define a strict weak ordering; bugs in compare logic break the heap property.
• Handles for decrease-key: store indices or references if you need to adjust arbitrary elements.
• Stability: heap operations and heapsort are not stable by default.
• Memory: array-backed heaps are contiguous and cache-friendly; linked variants trade locality for features like meld.

Example: Insert and Extract

function insert(A, x):
  A.append(x)
  i = length(A) - 1
  while i > 0 and A[i] < A[parent(i)]:
    swap A[i], A[parent(i)]
    i = parent(i)

function extractMin(A):
  if length(A) == 0: error
  minVal = A[0]
  A[0] = A[last]; remove last
  siftDown(A, 0, length(A))
  return minVal

When to Use Heaps

Use a heap when you repeatedly need the global min/max, or must interleave inserts with prioritized removals. If you need sorted iteration of all elements, a balanced BST or sort may be better; if you need fast membership tests, consider hash-based structures.

Next Topic