Heaps & Priority Queues

A tree that lives in an array and always keeps its smallest (or largest) element one step away

Introduction

A BST keeps everything fully sorted, which is more than most problems actually need. Often you only care about one thing: what's the smallest (or largest) item right now? A heap answers that question in O(1), and still supports insert and remove in O(log n), by relaxing the BST's ordering down to a much weaker rule. That relaxed rule is also what a priority queue is built on: instead of "first in, first out", it's "most important out first", and a heap is the standard way to implement one.

The Heap Property

A min-heap is a binary tree where every parent is smaller than or equal to both of its children. Unlike a BST, there's no rule relating left to right, only parent to child, which is a much easier invariant to maintain. A max-heap is the same idea flipped: every parent is larger than or equal to its children.

A Min-Heap

Figure 1: Every parent is smaller than its children, left vs right is never compared

Because the smallest value is always forced to the root, peek() is O(1), no searching required. And crucially, a heap is always a complete binary tree: every level is completely filled before the next one starts, and the last level fills left to right with no gaps.

Why a Heap Lives in an Array

Completeness means there are never any gaps, so instead of Lesson 7's left/right pointers, a heap can store its values in a single flat list (Lesson 2) and calculate every relationship with plain index arithmetic:

def parent(i: int) -> int:
    return (i - 1) // 2

def left_child(i: int) -> int:
    return 2 * i + 1

def right_child(i: int) -> int:
    return 2 * i + 2

Here is the same min-heap from Figure 1 laid out as that flat array. Reading the tree level by level, top to bottom and left to right, gives the array order. The element at index 1 finds its two children purely by arithmetic:

The Min-Heap from Figure 1, Stored as an Array

Figure 2: Index 1 (amber, value 3) has its children at 2·1+1 = 3 and 2·1+2 = 4 (blue, values 5 and 8). No child pointers are stored, the positions are computed.

No pointers, no wasted memory, and array indexing is O(1), so moving to a parent or child is exactly as fast as following a pointer would have been, without paying the per-node pointer overhead a linked structure needs.

Sift Up and Sift Down

Both heap operations follow the same idea: make one small local change, then let it "bubble" to wherever the heap property demands it goes.

push(): Sift Up

Add the new value at the next open slot (the array's end), then repeatedly swap it with its parent until the parent is smaller or it reaches the root.

pop(): Sift Down

Save the root's value, move the array's last element to the root, then repeatedly swap it with its smaller child until it's smaller than both.

class MinHeap:
    def __init__(self) -> None:
        self._data: list[int] = []

    def push(self, value: int) -> None:
        self._data.append(value)          # add at the end, the next free slot
        self._sift_up(len(self._data) - 1)

    def _sift_up(self, index: int) -> None:
        while index > 0:
            parent = (index - 1) // 2
            if self._data[index] < self._data[parent]:
                self._data[index], self._data[parent] = self._data[parent], self._data[index]
                index = parent
            else:
                break   # heap property restored, no need to go further

    def pop(self) -> int:
        if not self._data:
            raise IndexError("pop from an empty heap")
        smallest = self._data[0]
        last = self._data.pop()           # O(1): removing the array's last element
        if self._data:
            self._data[0] = last          # move it to the root...
            self._sift_down(0)            # ...then sink it into place
        return smallest

    def _sift_down(self, index: int) -> None:
        size = len(self._data)
        while True:
            left, right = 2 * index + 1, 2 * index + 2
            smallest = index
            if left < size and self._data[left] < self._data[smallest]:
                smallest = left
            if right < size and self._data[right] < self._data[smallest]:
                smallest = right
            if smallest == index:
                break
            self._data[index], self._data[smallest] = self._data[smallest], self._data[index]
            index = smallest

    def peek(self) -> int:
        if not self._data:
            raise IndexError("peek from an empty heap")
        return self._data[0]

heap = MinHeap()
for value in [5, 3, 8, 1, 9, 2]:
    heap.push(value)

print(heap.peek())

result = []
while heap._data:
    result.append(heap.pop())
print(result)

Expected Output:

1
[1, 2, 3, 5, 8, 9]

Why O(log n)

A complete binary tree with n nodes has height O(log n), the same logarithmic shrink from Lesson 8's balanced BSTs. Sift up and sift down each move at most one step per level, so both operations are bounded by that height.

Python's `heapq` Module

Python's standard library already ships a min-heap, implemented directly on top of a plain list using the same index math above. There's no dedicated heap type, just functions that operate on a regular list and keep it in heap order:

import heapq

numbers = [5, 3, 8, 1, 9, 2]
heapq.heapify(numbers)      # O(n): reorders the list in place, no new list needed
print(numbers[0])           # the smallest value is always at index 0

heapq.heappush(numbers, 0)
print(heapq.heappop(numbers))

Expected Output:

1
0

heapq only provides a min-heap. To get max-heap behavior, negate every value going in and negate it again coming out:

import heapq

max_heap: list[int] = []
for value in [5, 3, 8, 1, 9, 2]:
    heapq.heappush(max_heap, -value)   # negate going in

print(-max_heap[0])                    # negate again coming out
print(-heapq.heappop(max_heap))

Expected Output:

9
9

Note: heapq.heapify() converts an existing list into heap order in O(n), not O(n log n). Sifting down from the bottom half of the array upward turns out to do far less total work than calling push() n times would, a classic case where the obvious bound isn't the tight one.

Priority Queues

A priority queue is an abstract concept: a queue where each item has a priority, and the highest-priority item is always served next, regardless of insertion order. A heap is simply the standard, efficient way to implement one. Common uses include:

Task scheduling - an OS scheduler picking the next highest-priority process to run
Event simulation - always processing whichever event has the earliest timestamp next
Graph algorithms - Dijkstra's shortest path always expands the closest unvisited node next, a min-heap makes that O(log n) instead of an O(n) scan

Bonus: The Top K Elements Pattern

Find the k largest values in a list. Sorting everything first is O(n log n) and throws away most of the work. A heap solves it in O(n log k) by only ever tracking k candidates at once:

import heapq

def top_k_largest(numbers: list[int], k: int) -> list[int]:
    # A min-heap that never grows past size k: anything smaller than the
    # current smallest of the top k gets discarded immediately
    heap: list[int] = []
    for number in numbers:
        if len(heap) < k:
            heapq.heappush(heap, number)
        elif number > heap[0]:
            heapq.heapreplace(heap, number)   # pop the smallest, push the new one
    return sorted(heap, reverse=True)

data = [5, 3, 8, 1, 9, 2, 7]
print(top_k_largest(data, 3))
print(heapq.nlargest(3, data))   # the standard-library equivalent

Expected Output:

[9, 8, 7]
[9, 8, 7]

The heap holds the smallest of the current top k, so any new number only needs to beat that one weakest member to earn a spot, everything else can be skipped in O(1) with a single comparison. heapq.nlargest is the standard-library version of exactly this idea.

Key Takeaways

A heap only orders parent vs child, not left vs right, a much weaker (and cheaper to maintain) rule than a BST's
Completeness lets a heap live in a flat array - parent and child indices are computed, not stored as pointers
push and pop are O(log n), bounded by the tree's height, exactly like a balanced BST
peek is O(1) - the smallest (or largest) element is always sitting at index 0
Priority queues are the abstract idea, heaps are the implementation, and Python's heapq gives you one for free

Back to "Binary Search Trees"

Data Structures & AlgorithmsLesson 9

Next: "Self-Balancing Trees"

Heaps & Priority Queues

Introduction

The Heap Property

Why a Heap Lives in an Array

Sift Up and Sift Down

push(): Sift Up

pop(): Sift Down

Expected Output:

Why O(log n)

Python's heapq Module

Expected Output:

Expected Output:

Priority Queues

Bonus: The Top K Elements Pattern

Expected Output:

Key Takeaways

Python's `heapq` Module