Heaps in Python

A heap is a specialized tree-based structure that satisfies the heap property. Heaps are commonly used to implement priority queues, scheduling systems, and efficient selection problems (top-k).

Introduction to Heaps

Min-Heap

• Smallest element at the root
• Parent <= children

Max-Heap

• Largest element at the root
• Parent >= children

Important: Heaps are not fully sorted; they only guarantee ordering between parent and child.

Implementing Heaps Using Lists/Arrays

Python uses arrays (lists) internally for heaps. For a node at index i:

• left child = 2*i + 1
• right child = 2*i + 2
• parent = (i - 1) // 2

Python provides min-heap via heapq.

import heapq

heap = []
heapq.heappush(heap, 10)
heapq.heappush(heap, 5)
heapq.heappush(heap, 20)

print(heap)  # [5, 10, 20]

Heap Operations

Insertion (Push) — O(log n)

heapq.heappush(heap, 3)

Deletion (Pop smallest) — O(log n)

smallest = heapq.heappop(heap)
print(smallest)

Peek — O(1)

print(heap[0])

Heapify — O(n)

Converts a normal list into a heap efficiently.

nums = [10, 3, 5, 7]
heapq.heapify(nums)
print(nums)

Max Heap in Python

Python supports min-heap only, but you can simulate max-heap using negatives.

import heapq

max_heap = []
heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -20)

print(-heapq.heappop(max_heap))  # 20

Applications of Heaps

• Priority queue (tasks, CPU scheduling)
• Dijkstra algorithm (shortest path)
• Top K elements
• Merge K sorted lists
• Heap sort

Example: Top K largest elements

import heapq

nums = [5, 12, 3, 21, 7, 9]
k = 3
print(heapq.nlargest(k, nums))  # [21, 12, 9]

Summary

Heaps are essential when you need repeated access to the smallest/largest element efficiently. Master heapq, and many interview problems (top-k, scheduling, shortest path) become straightforward.