AI Hints
DSA in Python · Lesson 70 of 132

Heaps

The smallest always on top.

⏱ 2 min read▶ Video at 1:22:20🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

A hospital emergency room doesn't treat people in the order they arrive. The most urgent patient goes first. That's a priority queue, and the data structure behind it is called a heap.

Heaps
From the video: Heaps
  • The most urgent goes first
  • A priority queue
  • Built on a heap

The heap rule

A heap is a binary tree with one rule. Every parent is smaller than or equal to its children. So the smallest item is always at the top, the root. The tree is kept perfectly filled, level by level, which means it can be stored in a plain list, with no pointers at all.

Ruleparent ≤ children
Topalways the smallest
Shapefilled level by level
Stored ina plain list

Heap costs

Getting the smallest item is O of one, because it's always at the top. Adding an item, or removing the smallest, is O of log N. The item bubbles up or down one level at a time, and the tree is only log N levels tall. Building a heap from a list is O of N.

OperationCost
peek at the smallestO(1)
push a new itemO(log n)
pop the smallestO(log n)
build from a listO(n)

Summary

A heap keeps the smallest item at the top, with O of log N pushes and pops. It's the engine behind priority queues. Next, Python's heap module.

Key takeaways
  • Parent ≤ children
  • Smallest on top
  • O(log n) push and pop
Next up: heapq in Python — priority queues made easy