Heap (Priority Queue)

#How does it work?

A heap is a tree that always gives instant access to the smallest (min-heap) or largest (max-heap) element. Min-heap rule: every parent is smaller than or equal to its children, so the minimum sits at the root.

A heap is a complete binary tree: levels fill left to right without gaps. That lets it live in a plain array without pointers: the children of index i are at 2i + 1 and 2i + 2, and its parent at (i - 1) / 2.

Insert puts the new element at the end and moves it up while it is smaller than its parent (sift up). Extract-min moves the last element to the root and pushes it down while a child is smaller (sift down). A heap isn't sorted; it just answers "what's the smallest?" fast.

#Try it yourself

#Basic operations

insert(x)

Appends x to the array, then swaps it with its parent while it is smaller.

extractMin()

Removes the root, puts the last element there, and swaps it down with its smaller child.

peek()

Reads the minimum at the root without removing it.

heapify

Turns an arbitrary array into a heap in O(n).

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

class MinHeap:
    """Min-heap in a list: the children of i are 2i + 1 and 2i + 2, its parent is (i - 1) // 2."""

    def __init__(self) -> None:
        self.items: list[int] = []

    def push(self, value: int) -> None:
        a = self.items
        a.append(value)
        i = len(a) - 1
        # Sift up: swap with the parent while smaller.
        while i > 0 and a[(i - 1) // 2] > a[i]:
            a[i], a[(i - 1) // 2] = a[(i - 1) // 2], a[i]
            i = (i - 1) // 2

    def pop(self) -> int:
        a = self.items
        if not a:
            raise IndexError("heap is empty")
        smallest_value = a[0]
        last = a.pop()
        if a:
            a[0] = last  # move the last element to the root
            # Sift down: swap with the smaller child while a child is smaller.
            i = 0
            while True:
                left, right, smallest = 2 * i + 1, 2 * i + 2, i
                if left < len(a) and a[left] < a[smallest]:
                    smallest = left
                if right < len(a) and a[right] < a[smallest]:
                    smallest = right
                if smallest == i:
                    break
                a[i], a[smallest] = a[smallest], a[i]
                i = smallest
        return smallest_value

    def __len__(self) -> int:
        return len(self.items)


heap = MinHeap()
for v in (5, 3, 8, 1, 9, 2):
    heap.push(v)
# Popping repeatedly yields the values in ascending order.
print(*[heap.pop() for _ in range(len(heap))])

#Complexity

Because a heap is always a complete tree, its height is log₂ n, and sift up and sift down take at most that many steps. A heap keeps no order between siblings, so searching for an arbitrary value is O(n). Extracting all n elements one by one gives heap sort, which runs in O(n log n).

#When to use it?

The standard implementation of priority queues: OS task scheduling, Dijkstra's and Prim's algorithms, event simulations, "top k" problems and running medians. Python's heapq and Java's PriorityQueue are heaps.

#Practice

Log in to answer questions and save your progress.

#Up next

Lessons that build on this one:

• Dijkstra's Algorithm
• Heap Sort
• Huffman Coding