Heap Trees and Priority Queues

A heap tree is a specialized binary tree data structure that satisfies two fundamental constraints: a strict shape property and an ordering property. Together these constraints make heaps among the most practically useful data structures in computer science, powering everything from operating system schedulers to graph algorithms like Dijkstra's shortest path. Understanding heaps requires first grasping the shape they must maintain, then the rules governing how values are arranged within that shape, and finally the procedures that keep both properties intact as elements are inserted and removed.

The complete binary tree property is the shape constraint every heap must satisfy. A complete binary tree is one in which every level except possibly the last is fully filled, and on the last level all nodes are packed as far to the left as possible. This seemingly simple rule has a profound consequence: a complete binary tree with n nodes always has a height of exactly ⌊log₂ n⌋, which is O(log n). Because the height is logarithmically bounded by the number of elements, any operation that travels from root to leaf or leaf to root is guaranteed to touch at most O(log n) nodes. This is the geometric foundation that gives heaps their efficiency guarantees.

The complete binary tree shape also enables a remarkably efficient array-based representation that eliminates the need for pointer fields entirely. If the root is stored at index 0, then for any node stored at index i:

• Its left child is at index 2i + 1
• Its right child is at index 2i + 2
• Its parent is at index ⌊(i − 1) / 2⌋

These three formulas replace the left-pointer, right-pointer, and parent-pointer fields that a linked node representation would require. Because all nodes are packed into a contiguous block of memory, iteration and traversal benefit from cache locality — the processor can prefetch array elements efficiently, which is a significant real-world performance advantage over pointer-chasing through scattered heap-allocated nodes.

To make this concrete, consider a seven-element min-heap containing the values 3, 5, 8, 10, 12, 15, 20. The array representation and the logical tree look like this:

The tree is balanced by construction — no pointer bookkeeping needed, no rebalancing rotations as in AVL or red-black trees. The shape is enforced automatically by always adding or removing from the end of the array.

The ordering property determines how values are arranged among parent and child nodes, and it comes in two flavors. In a min-heap, every parent node holds a value less than or equal to both of its children. This means the minimum element in the entire collection is always at the root (index 0), available in O(1) time. In a max-heap, every parent holds a value greater than or equal to both of its children, placing the maximum element at the root.

A critical subtlety: the heap property is a local constraint between each parent–child pair. It says nothing about the relationship between siblings or between cousins. In the min-heap example above, the values 5 and 8 are siblings, and 5 happens to be less than 8, but that ordering is incidental — nothing in the heap property requires it. This partial ordering is intentional and is what allows the heap to be built and maintained so efficiently compared to a fully sorted structure.

The choice between a min-heap and a max-heap depends entirely on the application's needs. If you need rapid access to the smallest item — such as finding the task with the earliest deadline — a min-heap is the natural choice. If you need rapid access to the largest item — such as finding the highest-priority job in a job scheduler where higher numbers mean higher priority — a max-heap is appropriate. Any min-heap can be converted to a max-heap simply by negating all stored values, a common trick in languages or libraries that provide only one variant.

Insertion into a heap follows a two-phase process. First, the new element is appended to the end of the underlying array, which corresponds to placing it at the leftmost available position on the bottom level of the tree. This preserves the complete binary tree shape immediately. Second, the bubble-up (also called sift-up) procedure restores the ordering property.

Bubble-up works by repeatedly comparing the newly placed element with its parent. If the heap property is violated — for a min-heap, if the new element is smaller than its parent — the two are swapped. This process repeats, moving the element one level upward with each swap, until either the element reaches the root or its parent no longer violates the property. Because the tree height is O(log n), bubble-up performs at most O(log n) comparisons and swaps, giving insertion an O(log n) time complexity.

Here is a step-by-step example of inserting the value 4 into the seven-element min-heap from earlier:

• Step 1: Append 4 at index 7. Its parent is at index ⌊(7−1)/2⌋ = 3, which holds value 10. Since 4 < 10, swap them. Array: [3, 5, 8, 4, 12, 15, 20, 10]
• Step 2: Now 4 is at index 3. Its parent is at index ⌊(3−1)/2⌋ = 1, which holds value 5. Since 4 < 5, swap them. Array: [3, 4, 8, 5, 12, 15, 20, 10]
• Step 3: Now 4 is at index 1. Its parent is at index 0, which holds value 3. Since 4 > 3, no swap is needed. Bubble-up terminates.

The final array [3, 4, 8, 5, 12, 15, 20, 10] represents a valid min-heap. Notice that 4 bubbled up two levels in two comparisons, and the minimum (3) correctly remains at the root.

A clean Python-style pseudocode for insertion and bubble-up illustrates the logic:

def insert(heap, value):
    heap.append(value)          # Place at end (shape preserved)
    i = len(heap) - 1           # Index of new element
    while i > 0:
        parent = (i - 1) // 2
        if heap[i] < heap[parent]:   # Min-heap: child < parent → swap
            heap[i], heap[parent] = heap[parent], heap[i]
            i = parent
        else:
            break                    # Heap property satisfied

Removal from a heap almost always means removing the root — the element with the highest priority. This is the operation the heap is specifically designed to make efficient. Direct removal of the root would leave a gap that is hard to fill while preserving the complete binary tree structure. The standard solution is elegant: replace the root's value with the value of the last element in the array, then shrink the array by one. The complete tree shape is now preserved again. However, the ordering property is almost certainly violated — the value that was at the bottom of the tree is unlikely to be the smallest (or largest) in the heap. The bubble-down (also called sift-down or heapify-down) procedure then restores order.

Sift-down works as follows: starting from the root, compare the displaced element with its children. For a min-heap, swap it with the smaller of its two children if that child is smaller than the element itself. For a max-heap, swap it with the larger child if that child is larger. Repeat this process, moving downward, until the element is in a position where both children are at least as large (min-heap) or at most as large (max-heap) as it is, or until it reaches a leaf. Again bounded by the tree height, sift-down runs in O(log n) time.

Continuing the earlier example, remove the root (3) from [3, 4, 8, 5, 12, 15, 20, 10]:

• Step 1: Move last element (10) to root. Array becomes [10, 4, 8, 5, 12, 15, 20]. Size is now 7.
• Step 2: 10 is at index 0. Children are at index 1 (value 4) and index 2 (value 8). Smaller child is 4. Since 10 > 4, swap. Array: [4, 10, 8, 5, 12, 15, 20].
• Step 3: 10 is now at index 1. Children are at index 3 (value 5) and index 4 (value 12). Smaller child is 5. Since 10 > 5, swap. Array: [4, 5, 8, 10, 12, 15, 20].
• Step 4: 10 is now at index 3. Its children would be at indices 7 and 8, which are beyond the array bounds — it is a leaf. Sift-down terminates.

The resulting array [4, 5, 8, 10, 12, 15, 20] is a valid min-heap with the original minimum (3) removed. The new minimum (4) is correctly at the root.

def remove_min(heap):
    if len(heap) == 0:
        return None
    min_val = heap[0]
    heap[0] = heap[-1]      # Move last element to root
    heap.pop()              # Remove last position
    sift_down(heap, 0)
    return min_val

def sift_down(heap, i):
    n = len(heap)
    while True:
        left  = 2 * i + 1
        right = 2 * i + 2
        smallest = i
        if left < n and heap[left] < heap[smallest]:
            smallest = left
        if right < n and heap[right] < heap[smallest]:
            smallest = right
        if smallest == i:
            break           # Heap property satisfied
        heap[i], heap[smallest] = heap[smallest], heap[i]
        i = smallest

A priority queue is an abstract data type that generalizes the concept of a queue by associating each element with a priority and always serving the element with the highest priority first, regardless of insertion order. Priority queues appear in a wide range of applications: CPU scheduling (always run the highest-priority process), network packet routing, event-driven simulation (process the soonest event next), Huffman coding (always merge the two lowest-frequency nodes), and graph algorithms like Dijkstra's and Prim's.

The heap is the standard, most efficient general-purpose implementation of a priority queue. The table below compares the time complexities of priority queue operations across three common implementation strategies:

The heap delivers O(1) peek (the highest-priority element is always the root), O(log n) insertion via bubble-up, and O(log n) removal via sift-down. No other simple data structure achieves this balance. An unsorted array is fast to insert into but requires a full scan to find the minimum; a sorted array keeps the minimum at one end but requires shifting elements for each insertion. The heap's logarithmic guarantee for both critical operations makes it the right choice for workloads where both insertions and removals are frequent.

A min-heap naturally implements a min-priority queue, where smaller values represent higher priority (such as a task with an earlier deadline being more urgent). A max-heap naturally implements a max-priority queue, where larger values represent higher priority (such as a process with a higher priority number getting the CPU first). If a language's standard library provides only one type (Python's heapq module provides only a min-heap, for example), a max-heap can be simulated by negating all values before insertion and negating again after extraction.

The final major heap operation to understand is heapify — the process of converting an arbitrary, unordered array into a valid heap in-place. The naive approach would be to insert each of the n elements one by one using the standard insert operation, costing O(n log n) total. Heapify does the job in O(n) — a surprising and important result.

The insight behind heapify is that leaf nodes — roughly the bottom half of a complete binary tree — already trivially satisfy the heap property because they have no children. There is no need to process them. Heapify therefore starts at the last internal (non-leaf) node, which is at index ⌊(n/2) − 1⌋ in a zero-indexed array, and applies sift-down to every node from that index down to index 0 (the root).

def heapify(array):
    n = len(array)
    # Start from last non-leaf node, work up to root
    for i in range(n // 2 - 1, -1, -1):
        sift_down(array, i)

Why is this O(n) and not O(n log n)? The key is that nodes at greater depth (closer to the leaves) do far less work during sift-down. A node one level above the leaves can sift down at most 1 level; a node two levels above can sift down at most 2 levels; and so on. Summing the total work across all nodes — accounting for how many nodes exist at each depth and how many levels each can sift down — yields a geometric series that converges to O(n). The formal proof uses the fact that roughly n/2 nodes are leaves (0 work each), n/4 nodes are one level above leaves (at most 1 swap each), n/8 nodes are two levels above (at most 2 swaps each), and the total is bounded by 2n.

To see heapify in action, start with the unordered array [20, 15, 3, 10, 5, 8, 12]. With n = 7, the last non-leaf is at index ⌊7/2⌋ − 1 = 2.

• i = 2 (value 3): Children are index 5 (8) and index 6 (12). 3 is already smaller than both — no swap needed.
• i = 1 (value 15): Children are index 3 (10) and index 4 (5). Smaller child is 5 at index 4. Since 15 > 5, swap. Array: [20, 5, 3, 10, 15, 8, 12]. Now 15 is at index 4, which is a leaf — stop.
• i = 0 (value 20): Children are index 1 (5) and index 2 (3). Smaller child is 3 at index 2. Since 20 > 3, swap. Array: [3, 5, 20, 10, 15, 8, 12]. Now 20 is at index 2. Its children are index 5 (8) and index 6 (12). Smaller child is 8. Since 20 > 8, swap. Array: [3, 5, 8, 10, 15, 20, 12]. Now 20 is at index 5, a leaf — stop.

The final array [3, 5, 8, 10, 15, 20, 12] is a valid min-heap built from a random array in O(n) time. Verify: every parent is less than its children (3 < 5 and 8; 5 < 10 and 15; 8 < 20 and 12).

Heapify is the foundational first step in Heap Sort, one of the classic O(n log n) comparison-based sorting algorithms. Heap Sort heapifies the input array in O(n), then repeatedly extracts the maximum (using a max-heap) and places it at the end of the array, shrinking the heap by one each time. After n extractions, the array is sorted in ascending order entirely in-place. The complete algorithm runs in O(n log n) worst-case time with O(1) auxiliary space — matching Merge Sort's time complexity while matching Quick Sort's space efficiency, though in practice it is often slower than both due to poorer cache behavior during the repeated sift-down operations.

Taken together, the complete binary tree shape, the parent–child ordering property, bubble-up for insertion, sift-down for removal, and the linear-time heapify procedure form a cohesive and elegant system. Heaps expose only O(1) access to the most important element and O(log n) cost for all modifications — a carefully balanced tradeoff that makes them the backbone of priority queues and a critical building block across algorithms and systems.