Heap
A Heap is a special type of complete binary tree that follows a specific ordering rule called the heap property.
Heaps are mainly used when we need to quickly access the smallest or largest element.
Heap = Complete Binary Tree + Heap Property
1. What is a Heap?
There are two main types:
Max Heap
The parent is greater than or equal to its children.
50 / \ 30 40 / \ / \ 10 20 25 35
For every node:
Parent >= Children
Therefore, the largest element is always at the root.
Maximum = 50
Min Heap
The parent is smaller than or equal to its children.
10 / \ 20 15 / \ / \ 30 40 25 35
For every node:
Parent <= Children
Therefore, the smallest element is always at the root.
Minimum = 10
2. Heap vs BST
This is very important because both use trees.
BST
50 / \ 30 70
Rule:
ALL values in left subtree < root ALL values in right subtree > root
Heap
Max Heap:
50 / \ 30 40
Rule:
Parent >= children
Notice that 30 and 40 don't have to be ordered relative to each other.
So:
BST is globally ordered, while Heap is only parent-child ordered.
3. Complete Binary Tree
A heap must be a complete binary tree.
A complete binary tree has:
- Every level completely filled except possibly the last.
- The last level is filled from left to right.
Example:
10 / \ 20 30 / \ / 40 50 60
This is complete.
But:
10 / \ 20 30 \ / 50 60
is not complete because the last level isn't filled from left to right.
4. Why Do We Use Complete Binary Trees?
Because a complete binary tree can be stored very efficiently inside an array.
For example:
10 / \ 20 30 / \ / \ 40 50 60 70
Can be stored as:
[10, 20, 30, 40, 50, 60, 70]
No pointers are required.
This is one of the most important ideas behind heaps.
5. Array Representation of Heap
For a 0-based array:
index = i
The formulas are:
Parent
parent = (i - 1) / 2
Left child
left = 2 * i + 1
Right child
right = 2 * i + 2
Example
Consider:
50 / \ 30 40 / \ / \ 10 20 25 35
Array:
Index: 0 1 2 3 4 5 6 Value: 50 30 40 10 20 25 35
For 50 at index 0:
Left child = 2(0) + 1 = 1 Right child = 2(0) + 2 = 2
So:
50 ├── index 1 → 30 └── index 2 → 40
For 30 at index 1:
Left child = 2(1)+1 = 3 Right child = 2(1)+2 = 4
Therefore:
30 ├── 10 └── 20
6. Max Heap
A Max Heap follows:
Parent >= Children
Example:
90 / \ 70 80 / \ / \ 40 50 60 30
The largest element is always:
root = 90
But notice:
70 and 80
are not necessarily sorted relative to each other.
That's okay.
7. Min Heap
A Min Heap follows:
Parent <= Children
Example:
10 / \ 20 15 / \ / \ 40 30 25 50
The smallest element is always:
root = 10
8. Heap Operations
The main heap operations are:
- Insert
- Get maximum/minimum
- Delete maximum/minimum
- Heapify
- Build heap
- Heap sort
The most important operations are:
Insert → O(log n) Delete root → O(log n) Get root → O(1)
9. Inserting Into a Heap
Let's create a Max Heap.
Start:
50
Insert:
30
50 / 30
Already valid.
Now insert:
40
50 / \ 30 40
Still valid.
Now insert:
60
First, because it must remain complete, put it at the next available position:
50 / \ 30 40 / 60
But:
60 > 30
So the heap property is violated.
We move 60 upward.
50 / \ 60 40 / 30
Now:
60 > 50
Still violated.
Move again:
60 / \ 50 40 / 30
Now the heap is valid.
This process is called:
Heapify Up / Bubble Up / Sift Up
10. Heapify Up
When inserting into a heap:
1. Add element at the end. 2. Compare it with its parent. 3. If heap property is violated, swap. 4. Continue upward.
For Max Heap:
if child > parent swap
For Min Heap:
if child < parent swap
Because the height of a complete binary tree is O(log n):
Insertion = O(log n)
11. Delete Root
Suppose we have a Max Heap:
90 / \ 70 80 / \ / \ 40 50 60 30
We want to remove the maximum element.
The maximum is at the root:
90
We cannot simply remove it because the tree structure must remain complete.
Instead:
Step 1
Move the last element to the root.
30 / \ 70 80 / \ / 40 50 60
Step 2
Now compare 30 with its children.
70 > 30 80 > 30
Take the larger child:
80
Swap:
80 / \ 70 30 / \ / 40 50 60
Again compare 30 with its children:
60 > 30
Swap:
80 / \ 70 60 / \ / 40 50 30
Now valid.
This process is called:
Heapify Down / Bubble Down / Sift Down
Therefore:
Delete root = O(log n)
12. Heapify Down
For a Max Heap:
1. Replace root with last element. 2. Compare with children. 3. Find the larger child. 4. Swap if child > parent. 5. Continue downward.
For a Min Heap:
Find the smaller child.
13. C++ Max Heap Using priority_queue
In C++, the easiest way to use a heap is:
#include <queue> priority_queue<int> pq;
By default:
priority_queue = Max Heap
Example:
#include <iostream> #include <queue> using namespace std; int main() { priority_queue<int> pq; pq.push(50); pq.push(30); pq.push(70); pq.push(20); pq.push(90); cout << pq.top(); return 0; }
Output:
90
Because 90 is the maximum.
14. Main priority_queue Functions
Insert
pq.push(50);
Complexity:
O(log n)
Get maximum
pq.top();
Complexity:
O(1)
Remove maximum
pq.pop();
Complexity:
O(log n)
Check empty
pq.empty();
Number of elements
pq.size();
15. Min Heap in C++
By default:
priority_queue<int>
is a Max Heap.
To create a Min Heap:
priority_queue<int, vector<int>, greater<int>> pq;
Example:
#include <iostream> #include <queue> #include <vector> using namespace std; int main() { priority_queue<int, vector<int>, greater<int>> pq; pq.push(50); pq.push(30); pq.push(70); pq.push(20); pq.push(90); cout << pq.top(); return 0; }
Output:
20
Because the smallest element is at the root.
16. Max Heap vs Min Heap
| Feature | Max Heap | Min Heap |
|---|---|---|
| Root | Largest | Smallest |
| Parent relation | Parent ≥ children | Parent ≤ children |
| C++ default | Yes | No |
top() | Maximum | Minimum |
| Insert | O(log n) | O(log n) |
| Remove root | O(log n) | O(log n) |
| Get root | O(1) | O(1) |
17. Heapify
Heapify means fixing a tree so that it satisfies the heap property.
For example:
30 / \ 50 40
For Max Heap, this is invalid because:
30 < 50
After heapify:
50 / \ 30 40
Heapify is commonly used during:
- Insertion
- Deletion
- Building a heap
- Heap sort
18. Building a Heap
Suppose we have:
[10, 30, 20, 5, 40, 50]
We can convert it into a heap.
There are two approaches:
Repeated insertion
Insert elements one by one.
Complexity:
O(n log n)
Bottom-up heap construction
Start from the last non-leaf node and heapify downward.
Complexity:
O(n)
This is an important DSA fact:
Building a heap using bottom-up heapify takes O(n), not O(n log n).
19. Leaf Nodes
In an array-based heap with n elements:
The leaf nodes start from approximately:
n / 2
For zero-based indexing, indices:
n/2 → n-1
are leaves.
Why?
Because these nodes don't have children.
Therefore, when building a heap, we don't need to heapify the leaves.
20. Heap Sort
Heap can also be used for sorting.
For ascending order, we can use a Max Heap.
Example:
Array: [40, 10, 30, 50, 20]
Build Max Heap:
50 / \ 40 30 / \ 10 20
Then repeatedly remove the maximum.
The elements become arranged in sorted order.
Heap Sort complexity:
Time = O(n log n) Space = O(1)
Heap Sort is therefore an important sorting algorithm.
You'll study sorting more deeply later in your roadmap.
21. Heap Applications
Heaps are extremely useful in real DSA problems.
1. Priority Queue
Example:
Emergency patients
The highest-priority patient should be processed first.
2. CPU Scheduling
Processes can have different priorities.
Process A → priority 5 Process B → priority 2 Process C → priority 10
A priority queue can select the highest priority.
3. Dijkstra's Algorithm
A min heap is commonly used to efficiently select the vertex with the smallest current distance.
You'll encounter this when studying:
Graphs
4. Top K Problems
Examples:
Top K largest numbers Top K smallest numbers Kth largest element Kth smallest element
Heaps are frequently used.
5. Merge K Sorted Lists
A min heap can efficiently select the smallest current element among multiple sorted lists.
22. Heap vs Stack vs Queue vs BST
| Structure | Main Idea | Important Operation |
|---|---|---|
| Stack | LIFO | Top |
| Queue | FIFO | Front |
| BST | Ordered tree | Search |
| Max Heap | Largest at root | Maximum |
| Min Heap | Smallest at root | Minimum |
23. Heap vs BST
This is a common interview question.
BST
50 / \ 30 70 / \ / \ 20 40 60 80
Inorder:
20 30 40 50 60 70 80
It maintains an ordering among the entire subtrees.
Max Heap
80 / \ 50 70 / \ / \ 20 40 30 60
Only this needs to be true:
Parent >= Children
There is no requirement that the left subtree is smaller than the right subtree.
Therefore:
BST → good for searching ordered data Heap → good for repeatedly getting min/max
24. Important Heap Complexities
| Operation | Complexity |
|---|---|
| Get min/max | O(1) |
| Insert | O(log n) |
| Delete root | O(log n) |
| Heapify | O(log n) |
| Build heap | O(n) |
| Heap sort | O(n log n) |
| Search arbitrary element | O(n) |
Notice the last one.
A heap is not designed for fast arbitrary searching.
If you want to find 37 inside a heap, you may need to check many nodes.
25. Why Search is O(n) in a Heap
Consider:
100 / \ 50 80 / \ / \ 20 40 60 70
Suppose we search for:
60
Knowing that:
60 < 100
doesn't tell us exactly which subtree contains it.
Unlike a BST, the heap doesn't give us a left/right search direction.
Therefore:
Search = O(n)
26. A Simple Mental Model
Think about a company hierarchy.
Max Heap
The most important person is at the top:
CEO / \ Manager Manager
The parent has higher priority than the children.
Min Heap
The person with the smallest value/priority is at the top.
The key idea is:
Heap cares about priority, not complete sorting.
Final Summary
Remember these 7 points:
1. Heap is a Complete Binary Tree. 2. Two main types: Max Heap → largest at root Min Heap → smallest at root 3. Max Heap: Parent >= Children 4. Min Heap: Parent <= Children 5. Insert: Add at end → Heapify Up O(log n) 6. Delete root: Replace with last → Heapify Down O(log n) 7. Get root: O(1)
C++ shortcut
// Max Heap priority_queue<int> pq;
// Min Heap priority_queue<int, vector<int>, greater<int>> pq;
And the roadmap connection is:
Binary Tree ↓ BST ↓ Heap ↓ Priority Queue ↓ Trie