Heap

Q: Does Python have a built-in heap?

Yes. The heapq module turns a regular list into a min-heap with functions such as heappush() and heappop(). For a max-heap, you can store negated numbers, and Python 3.14 and later also provide functions such as heappush_max().

Updated September 30, 20263 min read

In short

A heap is a tree-based data structure that keeps the smallest or largest item at its root, so you can read it in O(1) and remove it in O(log n) time.

What is a heap data structure?

A heap is a special kind of tree that satisfies the heap property. In a min-heap, every parent is smaller than or equal to its children, so the smallest item is always at the root; in a max-heap, every parent is greater than or equal to its children, so the largest item is at the root. The most common kind, the binary heap, is a complete binary tree, meaning every level is full except possibly the last, which fills from left to right.

Because the tree is complete, a binary heap is usually stored in a plain array with no pointers: the children of the item at index i sit at 2i + 1 and 2i + 2, and its parent is at (i - 1) / 2, rounded down. Reading the top item takes O(1) time. Inserting an item or removing the top takes O(log n), because the heap only swaps items along one path between the root and a leaf, and that path is about log n levels long. Building a heap from n existing items takes just O(n) with an operation called heapify.

Think of a hospital emergency room: patients are treated by urgency rather than arrival order, and the most urgent case is always next. That is exactly what a priority queue does, and heaps are the standard way to build one. Heaps are used in task schedulers, Dijkstra's shortest-path algorithm, finding the top k items in a large dataset, merging sorted files, and heap sort, which sorts in O(n log n) time.

The heap data structure has nothing to do with heap memory, the area where programs allocate objects at runtime and that a garbage collector cleans up; they only share a name. A heap is also only partially ordered: it guarantees the top item, but the rest is not sorted, and searching for an arbitrary value takes O(n). If you need all items in sorted order or fast lookups by value, a balanced binary search tree is a better fit.

Key takeaways

A min-heap keeps the smallest item at the root; a max-heap keeps the largest.
Peeking at the top is O(1), while inserting and removing the top are O(log n).
Building a heap from n items takes O(n) time.
A binary heap is usually stored in an array, with no pointers.
Heaps are the standard implementation of priority queues.

Example

A task priority queue with Python's heapqpython

import heapq

# heapq turns a plain list into a min-heap: the smallest item is at index 0
tasks = []
heapq.heappush(tasks, (3, "write docs"))  # push: O(log n)
heapq.heappush(tasks, (1, "fix production bug"))
heapq.heappush(tasks, (2, "review pull request"))

print(tasks[0])  # peek in O(1): (1, 'fix production bug')

# Pop always returns the lowest priority number first: O(log n) each
while tasks:
    priority, task = heapq.heappop(tasks)
    print(priority, task)  # 1, then 2, then 3

Readers ask

What is the difference between a heap and a binary search tree?

A binary search tree keeps all values in sorted order, so it can quickly find any value. A heap only guarantees that the smallest or largest value is on top, which makes it simpler and faster for priority-queue work but slow, O(n), for finding arbitrary values.

Is the heap data structure related to heap memory?

No. Heap memory is the region where a program allocates objects at runtime, and it is not organized as a heap data structure. The two concepts just share a name.

Does Python have a built-in heap?

Yes. The heapq module turns a regular list into a min-heap with functions such as heappush() and heappop(). For a max-heap, you can store negated numbers, and Python 3.14 and later also provide functions such as heappush_max().