Binary Heap Data Structure

Binary heaps provide the backbone for efficient priority queue implementations, enabling systems to always process the highest (or lowest) priority item first. Understanding this structure is crucial because it bridges the abstract need for prioritized access with the concrete reality of efficient, array-based storage. You will learn how a simple array can mimic a tree, and how clever index arithmetic maintains order with impressive $O(\log n)$ performance for core operations.

The Heap Property and Array Representation

A binary heap is a specialized complete binary tree that satisfies the heap property. In a max-heap, every parent node has a value greater than or equal to the values of its children; a min-heap reverses this relation, with each parent being less than or equal to its children. This property ensures the element with the highest (or lowest) priority is always at the root of the tree. The structure is "complete," meaning every level except possibly the last is fully filled, and nodes are as far left as possible.

The true power lies in its storage. Instead of using node objects with pointers, a binary heap is compactly stored in a standard array. This is possible because of the completeness property. Given a node at index $i$ in a zero-indexed array, you can find its family using simple arithmetic:

• Parent index: $\lfloor (i-1)/2\rfloor$
• Left child index: $2i+1$
• Right child index: $2i+2$

This mapping eliminates the memory overhead of pointers and leverages the cache efficiency of contiguous array access. Visualize the array [50, 30, 20, 15, 10, 8] as a tree: the root (50) is at index 0, its children (30, 20) are at indices 1 and 2, and so on.

Core Operations: Insert and Sift-Up

To insert a new element, you first place it at the end of the array—the next available position in the complete tree. This almost certainly violates the heap property. To restore it, you perform a sift-up (also called bubble-up or swim) operation.

The sift-up procedure compares the new node with its parent. If it violates the heap property (e.g., it's larger than its parent in a max-heap), you swap the two nodes. This comparison-and-swap process repeats, moving the node up the tree toward the root, until the heap property is satisfied or the node becomes the root.

The process only travels up the height of the tree. Since a complete binary tree with $n$ nodes has a height of $\lfloor {\log }_{2}n\rfloor$, the sift-up operation runs in $O(\log n)$ time. Here is the step-by-step logic for inserting value 45 into a max-heap:

1. Append 45 to the array at the last position.
2. Find its parent index: if the new index is i, parent is at $\lfloor (i-1)/2\rfloor$.
3. Compare 45 with its parent's value.
4. If 45 is greater, swap the two values. The node 45 is now at the parent's index.
5. Repeat from step 2 using the new index for 45, until 45 is no longer greater than its parent or it reaches the root.

Core Operations: Extract and Sift-Down

The extract operation (often extract-max or extract-min) removes and returns the root element—the one with the highest priority. After removal, you are left with a hole at the root. The strategy is to move the last element in the array (the rightmost leaf) into the root position and then repair the heap from the top down using a sift-down (also called bubble-down or sink) operation.

The sift-down procedure starts at the root. It compares the node with its children. If it violates the heap property (e.g., it is smaller than at least one child in a max-heap), you swap it with the larger of its two children (for a max-heap). This comparison-and-swap process repeats, moving the node down the tree, until the heap property is restored or the node becomes a leaf.

Like sift-up, sift-down traverses at most the height of the tree, resulting in $O(\log n)$ time complexity. The steps for extracting the max from a max-heap are:

1. Store the root value (to return later).
2. Replace the root value with the last element in the array.
3. Remove the last element from the array (decrease size).
4. Starting at index 0 (the new root), compare it with its left and right children.
5. If it is smaller than the larger child, swap with that larger child.
6. Move the current index to the child's position you swapped with and repeat from step 4 until no swap is needed or you reach a leaf.

Heap Construction and the Priority Queue Interface

You can build a heap from an unsorted array in $O(n)$ time using a heapify process. This is faster than inserting $n$ elements individually, which would be $O(n\log n)$. The algorithm starts at the last non-leaf node (at index $\lfloor n/2\rfloor -1$) and performs sift-down operations on each node all the way back to the root. This efficient bottom-up construction is a key advantage.

The binary heap is the classic implementation for the abstract priority queue data type. The priority queue interface supports:

• insert(item, priority): Add an item (implemented via heap insert).
• peek(): Return the highest-priority item (the root element).
• extract(): Remove and return the highest-priority item.

This makes heaps essential for algorithms like Heap Sort and graph algorithms like Dijkstra's Shortest Path and Prim's Minimum Spanning Tree, where you constantly need to access the "next best" element.

Common Pitfalls

1. Off-by-One Errors in Index Arithmetic: Using incorrect formulas for child/parent indices is the most common implementation bug. For a zero-indexed array, the correct formulas are always:

• Left child: $2i+1$
• Right child: $2i+2$
• Parent: $\lfloor (i-1)/2\rfloor$

Memorize these and double-check your loops to ensure they don't access indices >= heap_size.

1. Confusing Sift-Up with Sift-Down: Using the wrong repair operation will break the heap. Remember: sift-up is used after an insertion at the end of the heap (bottom-up repair). Sift-down is used after extracting the root and replacing it with the last element (top-down repair), and during the heapify process.

1. Ignoring Heap Boundaries During Sift-Down: When sifting down, a node may have zero, one, or two children. Your code must check that the calculated child indices are within the current bounds of the heap (< heap_size). Failing to do so leads to reading garbage data or accessing array out of bounds.

1. Assuming peek() is $O(\log n)$: Accessing the root element (e.g., array[0]) is a constant time $O(1)$ operation. A common misconception is that all heap operations are logarithmic. Only operations that change the structure (insert, extract) require the $O(\log n)$ repair work.

Summary

• A binary heap is a complete binary tree satisfying the heap property (max-heap or min-heap), stored efficiently in an array using simple index arithmetic to navigate parent-child relationships.
• The insert operation adds an element to the end and uses sift-up to restore the heap property, running in $O(\log n)$ time.
• The extract operation removes the root, replaces it with the last element, and uses sift-down to restore the heap property, also running in $O(\log n)$ time.
• A heap can be built from an unsorted array in $O(n)$ time using a bottom-up heapify process, which applies sift-down to non-leaf nodes.
• The primary application of the binary heap is implementing an efficient priority queue, a critical component in numerous scheduling and graph algorithms.