Binary Heaps
Binary heaps are a type of data structure that make it fast to get the smallest or largest item from a collection. They’re super common in algorithms and interviews.
What is a binary heap?
A binary heap is:
- A complete binary tree (filled level by level, left to right)
- That follows the heap property
There are two kinds:
1. Min-Heap
- The smallest element is always at the top (the root)
- Every parent ≤ its children
2. Max-Heap
- The largest element is always at the top
- Every parent ≥ its children
Example (Min-Heap)
2
/ \
5 8
/ \
9 10
- 2 is the smallest → always at the top
- Tree is filled left to right
- This is a valid min-heap
Important Things to Know
Not a Binary Search Tree
- Heaps do not keep things sorted
- You only know that the root is min (or max)
Usually Stored in an Array
No pointers needed!
- Parent index:
(i - 1) // 2 - Left child:
2i + 1 - Right child:
2i + 2
Common Operations
| Operation | Time Complexity |
|---|---|
| Peek min/max | O(1) |
| Insert | O(log n) |
| Remove min/max | O(log n) |
| Build heap | O(n) |
Why Use Binary Heaps?
- Priority queues
- Dijkstra’s algorithm
- Scheduling tasks
- Finding top-K elements
- Heap sort