Heap Operations

Why This Matters

Heaps are the backbone of priority queues and show up constantly in algorithm questions, from implementing Dijkstra's shortest path to understanding why heap sort achieves $O(n \log n)$ complexity. You're being tested on more than just knowing what a heap looks like; you need to understand why certain operations take $O(\log n)$ time while others run in $O(n)$, and when to use each operation in real algorithmic contexts.

Heaps exploit tree height to achieve efficiency. Every operation you'll study either moves elements up or down the tree (taking $O(\log n)$ time) or processes nodes level by level (sometimes achieving a surprising $O(n)$ bound). Don't just memorize the time complexities. Know which direction elements move and why that determines the cost.

---

Building and Restructuring Heaps

These operations create heap structure from scratch or restore it after violations. The core mechanism is comparing parent-child relationships and swapping when the heap property is violated.

Heapify (Sift Down)

Heapify restores the heap property at a single node. It assumes both subtrees below that node are already valid heaps, then "sift down" (bubble down) the node to its correct position by repeatedly swapping it with its larger child (max-heap) or smaller child (min-heap).

• Starts at the given node and compares it to its children
• If a child violates the heap property, swap the node with the appropriate child and repeat on the affected subtree
• $O(\log n)$ per call since the element may traverse the full height of the tree

When people say "heapify the whole array," they usually mean calling this sift-down procedure on every non-leaf node in bottom-up order. That process is Build Heap (below).

Build Heap

Build Heap transforms an unsorted array into a valid heap in $O(n)$ time. That's surprisingly faster than inserting $n$ elements one at a time.

How it works:

1. Start at the last non-leaf node (index $\lfloor n/2 \rfloor - 1$).
2. Call heapify (sift down) on that node.
3. Move to the previous index and repeat.
4. Continue until you've heapified the root (index 0).

Why $O(n)$ and not $O(n \log n)$? Most nodes live near the bottom of the tree. A node at depth $d$ only sifts down at most $h - d$ levels (where $h$ is the tree height). The leaves (roughly half the nodes) do zero work. The nodes one level above the leaves do at most 1 swap each. Only the root does up to $\log n$ work. When you sum all of this across every node, the series converges to $O(n)$.

---

Single-Element Operations

These operations add, remove, or modify individual elements while preserving heap structure. The key mechanism is "bubbling": moving elements up or down until the heap property is restored.

Insert

Insert adds a new element to the heap while maintaining the heap property.

1. Place the new element at the next available position (the end of the array).
2. Compare it with its parent (parent index: $\lfloor (i - 1) / 2 \rfloor$).
3. If it violates the heap property, swap with the parent.
4. Repeat step 2-3 until the element is in a valid position or becomes the root.

This "bubble up" process takes $O(\log n)$ worst case since the element might travel from leaf to root. This is the standard way to add elements to a dynamic heap, such as when data arrives one item at a time in a streaming scenario.

Delete (Extract Max/Min)

Extract Max (max-heap) or Extract Min (min-heap) removes and returns the root, which always holds the highest- or lowest-priority element.

1. Save the root's value (that's your return value).
2. Move the last element in the array to the root position.
3. Reduce the heap size by one.
4. Sift down the new root: compare it with its children and swap with the larger child (max-heap) or smaller child (min-heap).
5. Repeat step 4 until the heap property is restored.

$O(\log n)$ time because the sift-down may traverse the full height. This is the foundation of efficient priority queue dequeue operations.

You can also delete an arbitrary element (not just the root) if you know its index: replace it with the last element, reduce the size, then either bubble up or sift down depending on whether the replacement is larger or smaller than the original.

Increase/Decrease Key

Increase Key and Decrease Key modify an element's priority in place.

• Increase Key (in a max-heap): the element may now be larger than its parent, so bubble up.
• Decrease Key (in a max-heap): the element may now be smaller than a child, so sift down.
• In a min-heap, the directions reverse: decreasing a key bubbles up, increasing sifts down.

Both run in $O(\log n)$ time. These operations require knowing the element's index in the array, which is why priority queue implementations often maintain a separate index map (a hash map from element to array index).

These are critical for graph algorithms like Dijkstra's and Prim's, where edge relaxation requires updating a vertex's distance (priority) after discovering a shorter path.

---

Multi-Element and Sorting Operations

These operations process the entire heap or combine multiple heaps, leveraging the heap's structure for efficient bulk processing.

Heap Sort

Heap Sort is a two-phase, comparison-based sorting algorithm.

1. Build Heap on the input array. This takes $O(n)$.
2. Repeatedly extract the root:
   • Swap the root (max element in a max-heap) with the last element in the unsorted portion.
   • Shrink the heap size by one.
   • Sift down the new root to restore the heap property.
   • Repeat until the heap is empty.

Phase 2 performs $n - 1$ extractions, each costing $O(\log n)$, so the total is $O(n \log n)$.

Heap Sort is in-place ($O(1)$ extra space) because extracted elements fill the array from the back. However, it is not stable: equal elements may not preserve their original relative order.

Merge Heaps

Merge Heaps combines two heaps into one.

1. Concatenate the two arrays into a single array of size $n + m$.
2. Run Build Heap on the combined array.

This gives an $O(n + m)$ time complexity. More sophisticated heap variants (binomial heaps, Fibonacci heaps) can merge in $O(\log n)$ or even amortized $O(1)$, but for a standard binary heap, the concatenate-and-rebuild approach is what you should know.

A typical use case is combining priority queues from parallel processes or merging sorted streams.

---

Quick Reference Table

---

Self-Check Questions

1. Why does Build Heap run in $O(n)$ time even though it calls Heapify (an $O(\log n)$ operation) on $O(n)$ nodes?

2. Which two operations use the "bubble up" mechanism, and in what situation would you choose one over the other?

3. Compare Heap Sort with Merge Sort in terms of space complexity, stability, and worst-case time complexity.

4. If you're implementing Dijkstra's algorithm and need to update a vertex's distance, which heap operation do you use and why does it require $O(\log n)$ time?

5. You have an unsorted array of 1,000 elements and need to create a min-heap. Explain why calling Build Heap is more efficient than inserting elements one by one, and quantify the time complexity difference.