Heap Deep Dive

This lesson takes heaps from basic to real problem solving.

Heapify (turn list into heap)

import heapq

nums = [5, 2, 9, 1, 7]
heapq.heapify(nums)
print(nums)  # now heap structure

Get k smallest

import heapq

nums = [10, 4, 7, 1, 9, 2]
print(heapq.nsmallest(3, nums))  # [1,2,4]

Get k largest

import heapq
print(heapq.nlargest(2, nums))  # [10,9]

Merge sorted lists efficiently

import heapq

a = [1,4,7]
b = [2,5,8]
c = [3,6,9]

print(list(heapq.merge(a, b, c)))

Graph: heap use cases

flowchart TD
  A[Heap] --> B[Scheduling]
  A --> C[Top K]
  A --> D[Merging sorted streams]

Remember

• heapify is fast for building heap
• nsmallest/nlargest solve top-k problems
• merge is great for sorted streams