8.3 Heap Implementation and Applications

Heap Data Structure

Heaps are data structures built to handle priority-based operations efficiently. Their core strength is finding and removing the highest (or lowest) priority element in $O(\log n)$ time, which makes them the go-to choice for priority queues, scheduling systems, and sorting.

This section covers how to build heaps from arrays, how to use them for finding k-th elements and sorting, and when heaps are (and aren't) the right tool.

Building Heaps from Arrays

There are two distinct approaches to building a heap, and they have different time complexities. This is a common exam topic, so make sure you understand the difference.

Approach 1: Bottom-up heapify (the faster way)

The heapify procedure converts an existing array into a heap in-place. It works by treating the array as a complete binary tree and fixing heap violations from the bottom up.

1. Start at the last non-leaf node (index $\lfloor n/2 \rfloor - 1$ in a zero-indexed array).

2. For each node, compare it with its children and swap with the larger child (max-heap) or smaller child (min-heap) if the heap property is violated.

3. After a swap, continue sifting down the swapped node until it lands in a valid position.

4. Move to the next node toward the root and repeat.

The time complexity is $O(n)$, not $O(n \log n)$. This surprises a lot of people. The reason is that most nodes are near the bottom of the tree and only need to sift down a short distance. A formal proof uses the fact that the sum of heights across all nodes is $O(n)$.

Approach 2: Repeated insertion (the slower way)

You can also build a heap by starting with an empty heap and inserting elements one at a time. Each insertion places the new element at the next available position and then sifts it up to restore the heap property.

• Each insertion takes $O(\log n)$ in the worst case.
• Over $n$ elements, this gives $O(n \log n)$ total.

Applications of Heaps

Finding the k-th largest element

A min-heap of size $k$ can find the k-th largest element in an unsorted array without fully sorting it.

1. Insert the first $k$ elements into a min-heap.
2. For each remaining element in the array, compare it to the root (the current minimum in the heap).
3. If the element is larger than the root, remove the root and insert the new element. This keeps the heap holding the $k$ largest elements seen so far.
4. After processing all elements, the root of the min-heap is the k-th largest.

Time complexity: $O(n \log k)$, since each heap operation on a size-$k$ heap costs $O(\log k)$, and you process $n$ elements. When $k$ is much smaller than $n$, this is significantly faster than sorting the whole array.

Finding the k-th smallest element works the same way but uses a max-heap of size $k$. You replace the root whenever you encounter a smaller element. The time complexity is still $O(n \log k)$.

Heaps in Sorting Algorithms

Heap Sort

Heap Sort uses a max-heap to sort an array in ascending order. It works in two phases:

1. Build a max-heap from the input array using bottom-up heapify ($O(n)$).

2. Extract elements one by one:

   • Swap the root (the maximum) with the last element in the unsorted portion.
   • Shrink the heap size by one (the swapped element is now in its final sorted position).
   • Sift the new root down to restore the heap property.

3. Repeat step 2 until the heap is empty.

• Time complexity: $O(n \log n)$ in all cases (best, average, worst).
• Space complexity: $O(1)$ auxiliary space since it sorts in-place.
• Heap Sort is not stable: equal elements may change their relative order.

Priority Queues

A priority queue is an abstract data type where each element has an associated priority, and you always retrieve the element with the highest (or lowest) priority first. Heaps are the standard implementation.

• Min-heap backs a minimum priority queue (lowest value = highest priority).
• Max-heap backs a maximum priority queue (highest value = highest priority).
• Insertion: $O(\log n)$
• Extract-min/max: $O(\log n)$
• Peek at min/max: $O(1)$

Pros and Cons of Heaps

Advantages:

• $O(\log n)$ insertion and extraction of the min/max element.
• $O(1)$ peek at the min/max.
• Heap Sort is in-place with guaranteed $O(n \log n)$ worst-case performance.
• Simple array-based implementation with no pointers or extra memory overhead.

Disadvantages:

• Searching for an arbitrary element is $O(n)$ since the heap only guarantees a partial ordering (parent vs. children), not a full one.
• Updating an element's priority (decrease-key or increase-key) requires knowing the element's position. Without an auxiliary index, finding it costs $O(n)$.
• Heap Sort is not stable, so equal elements may be reordered.
• In practice, heaps have worse cache performance than algorithms like quicksort due to the non-sequential memory access pattern of sifting through tree levels.

When to choose a heap:

• Priority-based access is the primary operation (scheduling, event-driven simulations, Dijkstra's algorithm).
• You need guaranteed $O(n \log n)$ worst-case sorting and can't afford quicksort's $O(n^2)$ worst case.

When something else fits better:

• If you need to search for specific elements frequently, a balanced BST gives you $O(\log n)$ search.
• If stable sorting matters (preserving the order of equal elements), use Merge Sort instead of Heap Sort.
• If your data changes frequently and you need ordered traversal, a BST or balanced tree is more appropriate.