Heaps
The smallest always on top.
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.

- 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.
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.
| Operation | Cost |
|---|---|
| peek at the smallest | O(1) |
| push a new item | O(log n) |
| pop the smallest | O(log n) |
| build from a list | O(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