Heaps

A heap is a complete binary tree stored in an array where every parent is greater than or equal to its children (max-heap) or less than or equal (min-heap). It gives O(1) access to the min or max and O(log n) insert and extract.

Why It Matters

Heaps implement priority queues — used in heap sort, Dijkstra’s shortest path, task schedulers, and rate limiters. They’re also the backbone of many greedy algorithms.

Array Representation

A heap is stored as a flat array. For node at index i:

• Parent: (i - 1) // 2
• Left child: 2 * i + 1
• Right child: 2 * i + 2

Min-heap as tree:         As array:
       1                  [1, 3, 2, 7, 6, 4, 5]
      / \                  0  1  2  3  4  5  6
     3   2
    / \ / \
   7  6 4  5

Operations

Operation	Time
Find min/max	O(1)
Insert	O(log n) — bubble up
Extract min/max	O(log n) — bubble down
Build heap from array	O(n) — heapify

Code Example

import heapq
 
# Python's heapq is a min-heap
nums = [5, 3, 8, 1, 2]
heapq.heapify(nums)       # O(n) — rearranges in-place
print(nums)                # [1, 2, 8, 5, 3] (heap property, not fully sorted)
 
# Extract min
smallest = heapq.heappop(nums)  # 1
print(smallest)
 
# Insert
heapq.heappush(nums, 0)
print(heapq.heappop(nums))  # 0
 
# Get k smallest/largest
data = [10, 4, 5, 8, 6, 11, 26]
print(heapq.nsmallest(3, data))  # [4, 5, 6]
print(heapq.nlargest(3, data))   # [26, 11, 10]
 
# Max-heap trick: negate values
max_heap = []
for val in [3, 1, 4, 1, 5]:
    heapq.heappush(max_heap, -val)
 
print(-heapq.heappop(max_heap))  # 5 (largest)
 
# Priority queue with (priority, item) tuples
tasks = []
heapq.heappush(tasks, (2, "low priority task"))
heapq.heappush(tasks, (0, "urgent task"))
heapq.heappush(tasks, (1, "medium task"))
 
while tasks:
    priority, task = heapq.heappop(tasks)
    print(f"[{priority}] {task}")
# [0] urgent task
# [1] medium task
# [2] low priority task

Heap Sort

Build a heap from the array, then repeatedly extract the min/max. O(n log n) time, O(1) extra space (in-place). Not stable.

When to Use a Heap

• Find the k smallest/largest elements in a stream
• Merge k sorted lists
• Dijkstra’s shortest path
• Median of a stream (two heaps: max-heap for lower half, min-heap for upper)
• Job scheduling by priority

Related

• Arrays — heaps are stored as arrays
• Trees and Binary Search Trees — heaps are binary trees with different invariants
• Stacks and Queues — a heap is a priority queue
• Sorting Algorithms — heap sort
• Greedy Algorithms — often use heaps