Data StructuresIntermediate16 min readUpdated March 2025

Heaps & Priority Queues

A heap is a complete binary tree that satisfies the heap property. It is the most efficient implementation of a priority queue, providing O(log n) insert and O(log n) extract-min/max, with O(1) peek at the minimum or maximum element.

Heap Properties

A heap is a complete binary tree (all levels filled except possibly the last, filled left to right) that satisfies the heap property:

- Min-Heap — Every parent node is smaller than or equal to its children. The minimum element is always at the root. - Max-Heap — Every parent node is larger than or equal to its children. The maximum element is always at the root.

Heaps are typically implemented as arrays (not as tree nodes with pointers). For a node at index i: - Left child is at index 2i + 1 - Right child is at index 2i + 2 - Parent is at index (i - 1) // 2

This array representation is cache-friendly and avoids pointer overhead.

Heap Operations: Insert and Extract

Two core heap operations:

Insert (push) — Add the new element at the end of the array, then "bubble up" (sift up) by swapping with parent until the heap property is restored. O(log n).
Extract-Min/Max (pop) — Remove the root, replace it with the last element, then "bubble down" (sift down) by swapping with the smaller/larger child until restored. O(log n).
Peek — Return the root element without removing it. O(1).
Heapify — Build a heap from an unsorted array in O(n) time (not O(n log n) as you might expect).

Min-Heap Implementation and heapq

Python's heapq module provides a min-heap. For a max-heap, negate the values:

python

import heapq

# ---- Python heapq (min-heap) ----
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 8)
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)

print(heap)                      # [1, 2, 8, 5, 4] (array representation)
print(heapq.heappop(heap))       # 1 (minimum)
print(heapq.heappop(heap))       # 2

# Build heap from list - O(n)
data = [5, 2, 8, 1, 4, 3]
heapq.heapify(data)
print(data)                      # [1, 2, 3, 5, 4, 8]

# Max-heap: negate values
max_heap = []
for val in [5, 2, 8, 1, 4]:
    heapq.heappush(max_heap, -val)
print(-heapq.heappop(max_heap))  # 8 (maximum)

# ---- Min-Heap from scratch ----
class MinHeap:
    def __init__(self):
        self._data = []

    def push(self, val):
        self._data.append(val)
        self._sift_up(len(self._data) - 1)

    def pop(self):
        if len(self._data) == 1:
            return self._data.pop()
        min_val = self._data[0]
        self._data[0] = self._data.pop()   # Move last to root
        self._sift_down(0)
        return min_val

    def peek(self):
        return self._data[0]

    def _sift_up(self, i):
        parent = (i - 1) // 2
        while i > 0 and self._data[i] < self._data[parent]:
            self._data[i], self._data[parent] = self._data[parent], self._data[i]
            i = parent
            parent = (i - 1) // 2

    def _sift_down(self, i):
        n = len(self._data)
        while True:
            smallest = i
            left, right = 2*i + 1, 2*i + 2
            if left < n and self._data[left] < self._data[smallest]:
                smallest = left
            if right < n and self._data[right] < self._data[smallest]:
                smallest = right
            if smallest == i:
                break
            self._data[i], self._data[smallest] = self._data[smallest], self._data[i]
            i = smallest

Applications: Heap Sort and K-th Largest

Heaps power several important algorithms:

python

import heapq

# ---- Heap Sort - O(n log n) ----
def heap_sort(arr):
    heapq.heapify(arr)
    return [heapq.heappop(arr) for _ in range(len(arr))]

print(heap_sort([5, 2, 8, 1, 4]))   # [1, 2, 4, 5, 8]

# ---- K Largest Elements - O(n log k) ----
def k_largest(arr, k):
    # Use a min-heap of size k
    # When heap exceeds k, pop the minimum
    heap = []
    for val in arr:
        heapq.heappush(heap, val)
        if len(heap) > k:
            heapq.heappop(heap)
    return sorted(heap, reverse=True)

print(k_largest([3, 1, 5, 12, 2, 11], 3))   # [12, 11, 5]

# ---- Merge K Sorted Lists - O(n log k) ----
def merge_k_sorted(lists):
    result = []
    heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))
    while heap:
        val, list_idx, elem_idx = heapq.heappop(heap)
        result.append(val)
        if elem_idx + 1 < len(lists[list_idx]):
            next_val = lists[list_idx][elem_idx + 1]
            heapq.heappush(heap, (next_val, list_idx, elem_idx + 1))
    return result

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

Key Takeaways

A heap is a complete binary tree stored as an array — parent at i, children at 2i+1 and 2i+2.
Min-heap: root is minimum; Max-heap: root is maximum. Both support O(log n) push and pop.
heapify builds a heap from an unsorted array in O(n) time — more efficient than n individual inserts.
Use a min-heap of size k to find the k largest elements in O(n log k) time.
Heaps power Dijkstra's shortest path, Prim's MST, heap sort, and task scheduling algorithms.

Contact Us

Have a question or feedback? Fill out the form below or reach us directly at support@nvaitraining.com