Heap & Priority Queue
DSA · Intermediate
Definition
A heap is a complete binary tree where each parent is smaller (min-heap) or larger (max-heap) than its children.
Heaps efficiently give the top-K elements, run Dijkstra, and schedule tasks.
Diagram
Flowchart
Example: K largest elements
import heapq
nums = [3,1,5,12,2,11]
print(heapq.nlargest(3, nums))Output: [12, 11, 5]
Complexity
push/pop O(log n) · peek O(1)
Key points
- Stored as an array
- Children of i are 2i+1 and 2i+2
- Python heapq is a min-heap
Interview questions
How to make a max-heap in Python?
Push negated values into heapq.
Build heap complexity?
O(n) using heapify.