Heaps: Implementation and Time Complexity Analysis

Understanding Heaps

A heap is a specialized tree-based data structure that satisfies the heap property: in a max-heap, every parent node is greater than or equal to its children; in a min-heap, every parent node is less than or equal to its children. The most common implementation is the binary heap, which is a complete binary tree typically stored in an array, where the root sits at index 0 or 1, and for any node at index i, its left child is at 2*i + 1 (or 2*i for 1-indexed) and its right child at 2*i + 2 (or 2*i + 1).

Heaps are not to be confused with the heap memory region used for dynamic allocation — they share the name but are entirely separate concepts. A heap data structure provides efficient access to the minimum or maximum element in constant time, and supports insertion and deletion in logarithmic time. This makes them the backbone of priority queues, which are ubiquitous in scheduler algorithms, Dijkstra's shortest path, Huffman coding, and event-driven simulation systems.

Why Heaps Matter

The heap's power lies in its ability to maintain a dynamic set of elements where you repeatedly need the smallest (or largest) item without resorting to a full sort each time. Consider these real-world scenarios:

• Task scheduling — an operating system kernel uses a priority queue to decide which process runs next, with priorities adjusted dynamically based on I/O wait times, CPU usage, and niceness values.
• Graph algorithms — Dijkstra's shortest path and Prim's minimum spanning tree rely on extracting the node with the smallest tentative distance or cheapest edge weight, operations that heaps optimize to O(log n) instead of O(n) for naive linear scans.
• Event simulation — discrete-event simulators keep future events in a min-heap keyed by timestamp, always processing the nearest event first.
• External sorting — the k-way merge phase of external mergesort uses a min-heap to efficiently find the smallest element among k sorted runs.
• Median tracking — two heaps (a max-heap for the lower half and a min-heap for the upper half) can maintain the median of a stream of numbers in O(log n) per insertion.

Without a heap, each extraction of the smallest element from an unsorted collection would require O(n) time. Over n extractions, that's O(n²) — unacceptable for large datasets. Heaps bring this down to O(n log n), matching the performance of sorting the entire collection once, but with the flexibility to interleave insertions and deletions efficiently.

Array-Based Binary Heap Implementation

The standard approach uses a flat dynamic array to represent the complete binary tree. The root is placed at index 1 (leaving index 0 unused for mathematical convenience) or at index 0. The 1-indexed version simplifies parent/child calculations: for node at index i, parent is at i // 2, left child at 2 * i, right child at 2 * i + 1. The 0-indexed version shifts these: parent at (i - 1) // 2, left child at 2 * i + 1, right child at 2 * i + 2.

Core Operations with Complete Code

Below is a full Python implementation of a min-heap using the 0-indexed convention. Each method includes the sift-up (bubble-up) and sift-down (bubble-down) helper functions that maintain the heap invariant.

class MinHeap:
    def __init__(self, items=None):
        """
        Initialize the heap. If an iterable of items is provided,
        build the heap in O(n) time using bottom-up heapify.
        """
        self.heap = []
        if items:
            self.heap = list(items)
            self._heapify()

    def __len__(self):
        return len(self.heap)

    def peek(self):
        """Return the smallest element without removing it."""
        if not self.heap:
            raise IndexError("peek on empty heap")
        return self.heap[0]

    def push(self, value):
        """Insert a new element, maintaining the heap invariant."""
        self.heap.append(value)
        self._sift_up(len(self.heap) - 1)

    def pop(self):
        """Remove and return the smallest element."""
        if not self.heap:
            raise IndexError("pop from empty heap")
        if len(self.heap) == 1:
            return self.heap.pop()
        root = self.heap[0]
        # Move the last element to the root and sift down
        self.heap[0] = self.heap.pop()
        self._sift_down(0)
        return root

    def pushpop(self, value):
        """
        Push a new element, then immediately pop the smallest.
        More efficient than separate push + pop for some use cases.
        """
        if not self.heap or value <= self.heap[0]:
            return value
        root = self.heap[0]
        self.heap[0] = value
        self._sift_down(0)
        return root

    def replace(self, value):
        """
        Pop the smallest element and push a new one simultaneously.
        Equivalent to pop() then push(), but more efficient.
        """
        if not self.heap:
            raise IndexError("replace on empty heap")
        root = self.heap[0]
        self.heap[0] = value
        self._sift_down(0)
        return root

    def _sift_up(self, idx):
        """Restore heap property from idx upwards (used after insert)."""
        while idx > 0:
            parent = (idx - 1) // 2
            if self.heap[idx] < self.heap[parent]:
                self.heap[idx], self.heap[parent] = self.heap[parent], self.heap[idx]
                idx = parent
            else:
                break

    def _sift_down(self, idx):
        """Restore heap property from idx downwards (used after pop)."""
        n = len(self.heap)
        while True:
            smallest = idx
            left = 2 * idx + 1
            right = 2 * idx + 2

            if left < n and self.heap[left] < self.heap[smallest]:
                smallest = left
            if right < n and self.heap[right] < self.heap[smallest]:
                smallest = right

            if smallest != idx:
                self.heap[idx], self.heap[smallest] = self.heap[smallest], self.heap[idx]
                idx = smallest
            else:
                break

    def _heapify(self):
        """
        Build a heap from an unordered array in O(n) time.
        Start from the last non-leaf node and sift down each.
        """
        n = len(self.heap)
        for i in range(n // 2 - 1, -1, -1):
            self._sift_down(i)

    def __str__(self):
        return str(self.heap)

Detailed Walkthrough of Each Operation

Push (Insert) — Append the new value to the end of the array, then call _sift_up. The element compares itself with its parent; if smaller (in a min-heap), they swap, and the process repeats upward. At most O(log n) swaps occur because the tree depth is logarithmic in the number of nodes.

Pop (Extract Min) — Save the root element (index 0), take the last element of the array and place it at the root, then call _sift_down. Starting from the root, compare with both children, swap with the smaller child, and continue downward until the heap property is restored. Again O(log n) due to tree depth.

Heapify (Build Heap) — Given an existing array, calling _sift_down on each element from the middle of the array down to index 0 builds a valid heap in O(n) time. This is counterintuitive — it seems like n/2 calls to an O(log n) operation would be O(n log n), but the majority of nodes are near the leaves and require very few sift-down steps. The sum of all node heights converges to O(n).

Pushpop and Replace — These combined operations save a full sift-up + sift-down cycle. Pushpop: if the new value is smaller than the current root, it would become the root anyway, so just return the new value. Otherwise, take the root, place the new value at the root, sift down, and return the old root. Replace does the same but always returns the old root. Both are O(log n).

Time Complexity Analysis

Per-Operation Complexity Table

For a binary heap containing n elements:

• Peek (get min/max) — O(1). The root is always at index 0.
• Push (insert) — O(log n) worst case. Amortized O(1) if the array resizing cost is amortized over many operations, but the sift-up still takes up to O(log n) swaps.
• Pop (extract min/max) — O(log n). Sift-down from root traverses at most the height of the tree.
• Heapify (build) — O(n). Proven via the convergence of the series sum of heights.
• Delete arbitrary element — O(log n) if you have its index. Change its value to -∞ (for min-heap), sift-up to root, then pop.
• Decrease/Increase key — O(log n). Adjust the value at a known index, then sift-up (if decreasing in min-heap) or sift-down (if increasing).
• Merge two heaps — O(n) for binary heaps (rebuild from concatenated arrays). Pairing heaps or Fibonacci heaps offer O(log n) or O(1) merge, at the cost of implementation complexity.

Mathematical Derivation of O(n) Heapify

The sift-down approach to building a heap processes nodes level by level from the bottom up. In a complete binary tree with height h, there are at most n/2^(h+1) nodes at height h. Each node may require up to h swaps. The total work is bounded by:

  Σ (h from 0 to ⌊log₂ n⌋)  (n / 2^(h+1)) * h
  = (n/2) * Σ (h / 2^h)
  ≤ (n/2) * 2
  = O(n)

The infinite sum Σ h / 2^h converges to exactly 2, which gives us the linear bound. This is one of the most elegant proofs in data structure analysis and explains why heap construction is so efficient in practice.

Amortized Analysis of Repeated Operations

Consider a sequence of k push operations followed by k pop operations on an initially empty heap. Each push is O(log n) and each pop is O(log n), so the total is O(k log k). However, if you push all elements first (building a heap via repeated insertion takes O(n log n) in the worst case) and then pop all, the total is O(n log n). Building via heapify first is O(n), then popping all is O(n log n), which is asymptotically the same total, but heapify gives a better constant factor for the build phase.

Advanced Variations and Real-World Usage

Max-Heap Adaptation

Converting the min-heap implementation to a max-heap requires only flipping the comparison operators in _sift_up and _sift_down. Alternatively, in languages like Python that support custom comparators, you can pass a comparator function. Another common trick is to negate values or use tuples with negative keys to reuse the same min-heap code for max-heap behavior.

# Using negation to turn Python's heapq (min-heap) into a max-heap
import heapq

values = [5, 3, 9, 1, 6]
max_heap = []
for v in values:
    heapq.heappush(max_heap, -v)  # Store negated

# Pop returns the negated smallest, so re-negate
largest = -heapq.heappop(max_heap)
print(largest)  # 9

Heap of Tuples for Priority Queues

When elements carry associated data, store tuples (priority, counter, item). The counter (often an incrementing integer) breaks ties when priorities are equal, preventing comparison of incomparable types. Python's heapq module uses this pattern internally.

import heapq
import itertools

counter = itertools.count()

pq = []
heapq.heappush(pq, (3, next(counter), "task A"))
heapq.heappush(pq, (1, next(counter), "task B"))  # Higher priority (smaller number)
heapq.heappush(pq, (3, next(counter), "task C"))  # Same priority as A, later counter

# Extracts "task B" (priority 1), then "task A", then "task C"
while pq:
    priority, _, task = heapq.heappop(pq)
    print(f"Executing: {task} with priority {priority}")

D-ary Heaps

A d-ary heap generalizes the binary heap by giving each node d children instead of 2. This reduces the tree height to log_d(n), making push operations faster (sift-up traverses shorter height), but pop operations slower because finding the minimum among d children at each step takes O(d) comparisons. For applications where push dominates pop, a 4-ary or 8-ary heap can outperform a binary heap. The optimal d often aligns with cache line sizes on modern hardware.

Fibonacci Heaps and Pairing Heaps

For graph algorithms with many decrease-key operations (like Dijkstra's algorithm on dense graphs), Fibonacci heaps provide amortized O(1) decrease-key and O(log n) delete-min. Pairing heaps offer similar practical performance with simpler implementation. However, binary heaps often win in practice for moderate n due to low constant factors and excellent cache locality from the array backing store.

Best Practices

• Use the standard library when available — Python's heapq, Java's PriorityQueue, C++'s std::priority_queue, and Rust's std::collections::BinaryHeap are battle-tested, highly optimized, and already handle edge cases. Only implement your own heap for learning or when you need custom behavior like delete-by-index.
• Prefer heapify over repeated push — If you have all elements upfront, call heapify() or the equivalent constructor. Building via n successive pushes is O(n log n) whereas heapify is O(n). This matters on datasets with millions of elements.
• Store immutable keys — If you mutate an element's key while it's in the heap, the heap invariant breaks. Either remove and re-insert, or use a heap that supports explicit decrease-key with a handle (like a Fibonacci heap).
• Watch for hidden O(n) operations — Searching for an arbitrary element in a binary heap is O(n) because heaps are not search trees. If you need fast membership queries and key updates, consider a balanced BST or a hashmap paired with the heap index.
• Profile before optimizing d — Switching to a 4-ary heap may improve throughput in I/O-bound systems where push latency matters, but for balanced workloads, the binary heap's simplicity often wins. Measure with realistic data.
• Thread safety — Standard heap implementations are not thread-safe. Wrap operations in locks if multiple threads push/pop, or use concurrent data structures like PriorityBlockingQueue in Java.
• Memory layout matters — The array-based binary heap has superb cache performance because parent-child traversal follows predictable arithmetic patterns. A pointer-based tree heap would incur cache misses at every level. Stick to array-backed heaps for performance-critical code.

Debugging Heap Implementations

When writing your own heap, these sanity checks catch most bugs:

def _assert_heap_invariant(heap):
    """Verify min-heap property holds for all nodes."""
    n = len(heap)
    for i in range(n):
        left = 2 * i + 1
        right = 2 * i + 2
        if left < n:
            assert heap[i] <= heap[left], f"Violation at {i} -> left {left}"
        if right < n:
            assert heap[i] <= heap[right], f"Violation at {i} -> right {right}"

# Quick test
h = MinHeap([3, 1, 6, 5, 2, 4])
_assert_heap_invariant(h.heap)
print("Heap invariant holds after heapify")

for val in [0, 7, -1]:
    h.push(val)
    _assert_heap_invariant(h.heap)
print("Invariant holds after pushes")

while len(h) > 0:
    prev = h.pop()
    if len(h) > 0:
        assert prev <= h.peek(), "Pop order violated"
print("Elements popped in ascending order")

Run invariant checks after every mutating operation during development. The assertion overhead is negligible for debugging but catches off-by-one errors in child index calculations and comparison direction mistakes.

Heaps in Algorithm Design: Complete Examples

Dijkstra's Shortest Path with Binary Heap

import heapq

def dijkstra(graph, start):
    """
    Compute shortest paths from start node in a weighted graph.
    graph: adjacency dict mapping node -> list of (neighbor, weight)
    Returns: dict of node -> shortest distance from start
    """
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]  # (distance, node)
    visited = set()

    while pq:
        dist, current = heapq.heappop(pq)
        if current in visited:
            continue
        visited.add(current)

        for neighbor, weight in graph[current]:
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))

    return distances

# Example usage
graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('C', 1), ('D', 5)],
    'C': [('D', 8), ('E', 10)],
    'D': [('E', 2)],
    'E': []
}
print(dijkstra(graph, 'A'))
# Output: {'A': 0, 'B': 4, 'C': 2, 'D': 9, 'E': 11}

K-Way Merge Using Heap

import heapq

def k_way_merge(sorted_lists):
    """
    Merge k sorted lists into one sorted list using a min-heap.
    Each input list must be already sorted.
    """
    result = []
    # Heap entries: (value, list_index, element_index)
    heap = []
    for i, lst in enumerate(sorted_lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))

    while heap:
        val, list_idx, elem_idx = heapq.heappop(heap)
        result.append(val)
        # Advance in the same list
        next_elem_idx = elem_idx + 1
        if next_elem_idx < len(sorted_lists[list_idx]):
            heapq.heappush(heap, (
                sorted_lists[list_idx][next_elem_idx],
                list_idx,
                next_elem_idx
            ))

    return result

# Example
lists = [
    [1, 4, 7],
    [2, 5, 8],
    [3, 6, 9]
]
merged = k_way_merge(lists)
print(merged)  # [1, 2, 3, 4, 5, 6, 7, 8, 9]

Running Median with Dual Heaps

import heapq

class RunningMedian:
    """
    Maintain median of a stream using a max-heap for the lower half
    and a min-heap for the upper half. Python's heapq is a min-heap,
    so we negate values for the max-heap behavior.
    """
    def __init__(self):
        self.low = []   # max-heap (stored as negated values)
        self.high = []  # min-heap

    def add(self, num):
        # Push to appropriate half
        if not self.low or num <= -self.low[0]:
            heapq.heappush(self.low, -num)
        else:
            heapq.heappush(self.high, num)

        # Balance sizes: low can have at most 1 more element than high
        if len(self.low) > len(self.high) + 1:
            moved = -heapq.heappop(self.low)
            heapq.heappush(self.high, moved)
        elif len(self.high) > len(self.low):
            moved = heapq.heappop(self.high)
            heapq.heappush(self.low, -moved)

    def median(self):
        if len(self.low) > len(self.high):
            return -self.low[0]
        elif len(self.low) == len(self.high) and self.low:
            return (-self.low[0] + self.high[0]) / 2.0
        return None

# Stream example
stream = RunningMedian()
for num in [5, 2, 9, 1, 7, 6, 3]:
    stream.add(num)
    print(f"Added {num}, median: {stream.median()}")

Conclusion

Heaps are one of the most elegant and practical data structures in computer science. Their array-based implementation delivers O(1) access to the extremum, O(log n) insertions and deletions, and O(n) construction — all with a compact memory footprint and excellent cache locality. Whether you're implementing a job scheduler, optimizing a graph algorithm, merging sorted files, or tracking streaming statistics, the heap's simplicity and predictable performance make it the right tool for the job. Understanding the sift-up and sift-down mechanics, the linear-time heapify proof, and the tradeoffs between binary, d-ary, and more exotic heap variants gives you both the theoretical grounding and the practical engineering judgment to choose and implement the right heap for your specific constraints. When in doubt, reach for your language's standard heap implementation first — then customize only when you've measured a bottleneck that a generic solution cannot address.