heapq
Python's standard-library module of functions that treat an ordinary list as a binary min-heap.
In more detail
heappush and heappop add and remove the smallest item in O(log n); heapify builds a heap in O(n); nlargest and nsmallest return the top k items efficiently; merge merges sorted inputs. Entries are often tuples such as (priority, task), which compare by priority first.
Example
heapq.heappush(h, (2, "write report")); heapq.heappop(h)Related terms
- binary heap — A complete binary tree stored in an array in which every parent is ordered before its children, so the smallest (or largest) item is always at the root.
- min-heap — A heap in which every parent is less than or equal to its children, so the minimum is at the root; a max-heap reverses the order.
- priority queue — A collection where each item has a priority and the item removed next is always the one with the highest priority, not the oldest.
- heapify — Rearranging an unordered list into a valid heap in place, which Python's heapq.heapify does in linear time.
- k-way merge — Merging k sorted sequences into one by keeping the current front item of each in a min-heap and repeatedly taking the smallest.
Taught in
- Sorting In Real Systems: Stability, Keys And External Sort — Algorithms & Data Structures for Working Engineers
- Heaps And Priority Queues — Algorithms & Data Structures for Working Engineers
- Dijkstra: Shortest Paths With A Priority Queue — Algorithms & Data Structures for Working Engineers