A heap is a tree-shaped structure that keeps the smallest or largest value easy to access. In Python, heapq implements a min-heap using a list.
Heaps are useful when the algorithm repeatedly needs the current best candidate.
Core Idea
A heap does not keep every element fully sorted. It only maintains enough order to remove the smallest item efficiently.
In Python’s heapq, heappush adds an item and heappop removes the smallest item. Each operation is O(log n).
The important guarantee is at the top: the smallest item is available at index 0. The rest of the internal list is arranged to preserve the heap property, not to look sorted.
Usage Contract
Python’s heapq functions expect a list that is treated as a heap. Use heapq.heappush(heap, item) to add an item and heapq.heappop(heap) to remove the smallest item.
If items are tuples, Python compares them from left to right. Put the priority first, such as (priority, item), when the heap should be ordered by priority.
Python Example
import heapq
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 8)
smallest = heapq.heappop(heap)smallest is 2.
Why Not Sort Every Time?
If the algorithm repeatedly adds candidates and removes the smallest one, sorting the whole list after every insertion is wasteful. A heap maintains just enough structure to support efficient repeated minimum extraction.
For example, Dijkstra’s algorithm repeatedly asks for the unprocessed vertex with the smallest known distance. A heap fits that pattern better than scanning every vertex each time.
Max-Heap Pattern
Python’s heapq is a min-heap. To simulate a max-heap for numbers, store negative values:
heap = []
heapq.heappush(heap, -10)
heapq.heappush(heap, -3)
largest = -heapq.heappop(heap)largest is 10.
Complexity
heappush and heappop are O(log n). Reading the smallest item at heap[0] is O(1), but removing it correctly requires heappop.
Building a heap from an existing list with heapq.heapify(values) is O(n).
Common Confusions
A heap is not a sorted list. Looking at the internal list may not show sorted order.
Python’s heapq is a min-heap. For max-heap behavior, a common technique is to store negative numbers or reversed priorities.
A heap is useful for repeated best-item extraction. If the algorithm needs all items in sorted order once, sorted(values) may be simpler.
When To Use It
Use a heap for top-k problems, scheduling, merging sorted streams, and graph algorithms that repeatedly choose the lowest-cost candidate.
The signal is repeated access to the current minimum or maximum while the candidate set changes.
The Main Point
A heap gives fast access to the smallest item without fully sorting everything. It is useful when the next item must be repeatedly chosen by priority.