Data Structures

Heap Data Structure Explained: Min-Heaps, Max-Heaps, and Priority Queues

A heap is a complete binary tree stored in an array where every parent satisfies a size relationship with its children. Min-heaps keep the smallest element at the root; max-heaps keep the largest. Both enable O(log n) insert and extract with O(1) access to the priority element.

Published June 30, 2026

When you need to repeatedly pull the smallest (or largest) element from a growing collection, a heap is the right tool. A sorted array lets you access the minimum in O(1) but insert in O(n). A heap gives you O(log n) for both operations and O(1) for peeking at the top. This asymptotic balance makes heaps the backbone of priority queues, Dijkstra's shortest-path algorithm, heap sort, and scheduling systems in operating systems.

A heap is stored as an ordinary array rather than a linked structure. For a node at index i, its left child sits at 2i + 1, its right child at 2i + 2, and its parent at (i - 1) // 2. This layout is cache-friendly and avoids pointer overhead entirely.

Operations and Complexity

Operation	Time Complexity	Notes
Peek (find-min or find-max)	O(1)	Root is always the priority element
Insert (push)	O(log n)	Append to end, sift up
Extract (pop)	O(log n)	Remove root, place last element at root, sift down
Heapify (build from list)	O(n)	Sift down from n/2 to 0; tighter than n log n
Delete arbitrary element	O(log n)	Requires knowing the index; not supported by heapq directly
Heap sort (full)	O(n log n)	In-place, but poor cache behavior vs quicksort in practice

How Heapify Works

Building a heap from an unsorted list takes O(n) time, not O(n log n) as you might expect. The trick is to start from the last internal node (at index n//2 - 1) and sift each node down to its correct position, working backwards to the root. Nodes near the leaves do almost no work because they have little tree below them, and the math works out to a linear bound.

This is significantly faster than inserting n elements one at a time (each insert costs O(log n), giving O(n log n) total). When you have the full dataset upfront, always prefer heapify over repeated pushes.

Python heapq: Priority Queue Operations

Python's standard library provides a min-heap through the heapq module. It operates on plain lists, which means you can inspect the underlying array at any time.

import heapq

# Build a heap from an existing list in O(n)
data = [5, 3, 8, 1, 9, 2, 7]
heapq.heapify(data)
print(data)  # [1, 3, 2, 5, 9, 8, 7] -- heap-ordered

# Push a new element
heapq.heappush(data, 4)

# Pop the smallest element
smallest = heapq.heappop(data)
print(smallest)  # 1

# Peek without removing
print(data[0])   # current minimum

# Push and pop in one atomic operation (more efficient)
result = heapq.heappushpop(data, 0)   # pushes 0, pops and returns 0
result = heapq.heapreplace(data, 99)  # pops first, then pushes 99

# Get n largest or n smallest without full sort
top3 = heapq.nlargest(3, data)
bot3 = heapq.nsmallest(3, data)

Simulating a Max-Heap

Python only provides a min-heap. The standard workaround is to negate the values: push -value instead of value, and negate again when popping.

max_heap = []
for val in [5, 3, 8, 1, 9]:
    heapq.heappush(max_heap, -val)

largest = -heapq.heappop(max_heap)
print(largest)  # 9

For objects, push tuples where the first element is the priority. The heap compares tuples element by element, so (priority, item) sorts by priority first:

task_queue = []
heapq.heappush(task_queue, (3, "low priority task"))
heapq.heappush(task_queue, (1, "urgent task"))
heapq.heappush(task_queue, (2, "medium task"))

priority, task = heapq.heappop(task_queue)
print(task)  # "urgent task"

Real-World Uses

Dijkstra's algorithm: A min-heap drives the priority queue that always processes the closest unvisited node next.
Median maintenance: Two heaps (a max-heap for the lower half, a min-heap for the upper half) keep the median accessible in O(1) with O(log n) inserts.
Task scheduling: Operating system schedulers and job queues use priority queues to decide which task runs next.
K-way merge: Merging k sorted lists or files uses a min-heap holding one element from each list, popping the minimum at each step.
Top-k problems: Maintaining a min-heap of size k lets you find the k largest elements in a stream in O(n log k) time with O(k) space.

When performance matters, prefer heapq.heapify over repeated heappush calls, and prefer heappushpop over separate push and pop when you need both. For the k-largest pattern, heapq.nlargest(k, iterable) uses an optimized implementation internally and is usually faster than sorting the full list when k is small relative to n.