Why should you care?
Imagine you have thousands of tasks, each with a different priority, and you always need to process the highest-priority task first.
Searching through all tasks every time would be expensive.
A heap provides an efficient way to repeatedly access the smallest or largest element while still allowing new elements to be added and removed.
Heaps are especially useful for:
- Priority queues
- CPU and task scheduling
- Finding the smallest or largest values
- Dijkstra's shortest-path algorithm
- Prim's minimum spanning tree algorithm
- Heap sort
- Streaming and top-K problems
Heaps are also important because they show how a tree can be represented efficiently using an array.
The Problem
Suppose a system receives these tasks:
Task A → Priority 5
Task B → Priority 2
Task C → Priority 8
Task D → Priority 1
The system should process the most important task first.
If we simply store them in an array:
[5, 2, 8, 1]
we would need to search through the collection to find the highest priority.
We could sort the entire collection, but that introduces unnecessary work whenever tasks are continuously being added and removed.
We need a structure that efficiently supports:
Add a value
Remove the highest/lowest value
See the highest/lowest value
That's the problem a heap solves.
The Concept
A heap is a specialized tree-based data structure that satisfies a specific ordering property.
There are two common types:
Min-Heap
The smallest element is always at the root.
10
/ \
20 30
/ \
40 50
The rule is:
Parent ≤ Children
Therefore:
Minimum element = Root
Max-Heap
The largest element is always at the root.
50
/ \
40 30
/ \
20 10
The rule is:
Parent ≥ Children
Therefore:
Maximum element = Root
The important thing to understand is that a heap is not fully sorted.
Only the parent-child relationship is guaranteed.
Simple Explanation
Think of a heap as a system that keeps the most important element at the top.
For a max-heap:
100
/ \
80 90
/ \ / \
40 60 70 50
Notice that 100 is at the top.
But the rest isn't completely sorted:
80
90
40
60
70
50
They don't have to be globally ordered.
The only requirement is:
Parent ≥ Child
So:
100 > 80
100 > 90
80 > 40
80 > 60
90 > 70
90 > 50
This limited ordering is what allows heaps to be efficient.
Real-world Analogy
Imagine an emergency room.
Patients arrive with different priority levels:
Patient A → Priority 3
Patient B → Priority 8
Patient C → Priority 5
Patient D → Priority 10
The patient with the highest priority should be handled first.
A max-heap can organize these priorities so that the highest-priority patient is always at the top.
Priority 10
/ \
Priority 8 Priority 5
When the priority-10 patient is processed, the heap reorganizes itself so that the next highest-priority patient moves to the top.
The system doesn't need to completely sort every patient after every operation.
It only needs to maintain the heap property.
Code Example
In Java, a heap is commonly used through PriorityQueue.
By default, Java's PriorityQueue behaves as a min-heap.
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
PriorityQueue<Integer> heap = new PriorityQueue<>();
heap.add(40);
heap.add(10);
heap.add(30);
heap.add(20);
System.out.println(heap.peek());
System.out.println(heap.poll());
System.out.println(heap.poll());
}
}
Output:
10
10
20
Notice that the smallest value is always available through:
heap.peek();
and removed through:
heap.poll();
Creating a Max-Heap
We can reverse the ordering:
PriorityQueue<Integer> maxHeap =
new PriorityQueue<>((a, b) -> b - a);
Now:
maxHeap.add(40);
maxHeap.add(10);
maxHeap.add(30);
maxHeap.add(20);
System.out.println(maxHeap.poll());
produces:
40
The largest value is now at the top.
Common Mistakes
Mistake 1: Thinking a heap is a sorted tree
A heap is not a sorted binary tree.
For example, this is a valid max-heap:
100
/ \
50 80
/ \ / \
20 30 40 70
But this is not globally sorted.
For example:
50
80
doesn't follow ascending order.
That's fine.
The heap only guarantees:
Parent ≥ Children
for a max-heap.
Mistake 2: Confusing a heap with a Binary Search Tree
A BST follows:
Left < Parent < Right
A max-heap follows:
Parent ≥ Children
Compare them:
BST:
50
/ \
30 70
Max-Heap:
70
/ \
50 60
In a BST, the left and right sides have different meanings.
In a heap, the important relationship is between a parent and its children.
A heap is primarily designed for quickly accessing the minimum or maximum element, not for arbitrary searching.
Mistake 3: Assuming every binary tree is a heap
A heap normally requires two properties:
1. Complete binary tree
2. Heap property
For example:
50
/ \
40 30
/ \
20 10
can be a valid max-heap.
But a structure like:
50
/
40
/
30
/
20
is not a complete binary tree and therefore is not a standard binary heap.
Advanced Notes
1. Complete Binary Tree
A binary heap is usually a complete binary tree.
This means:
- Every level is completely filled except possibly the last.
- The last level is filled from left to right.
For example:
10
/ \
20 30
/ \ /
40 50 60
This is complete.
But:
10
/ \
20 30
\ \
50 60
is not complete because nodes aren't filled from left to right.
This complete-tree property is what makes array-based heap storage possible.
2. Heap as an Array
One of the most interesting aspects of a heap is that we don't actually need node objects with explicit left and right references.
A heap can be stored directly in an array.
Consider:
10
/ \
20 30
/ \
40 50
The array representation is:
[10, 20, 30, 40, 50]
The relationships are determined by the indexes.
For a 0-based array:
Parent:
(i - 1) / 2
Left child:
2i + 1
Right child:
2i + 2
For example, if:
i = 1
then the element is 20.
Its children are:
2(1) + 1 = 3
2(1) + 2 = 4
So:
20
├── 40
└── 50
This is a beautiful example of how a tree structure can be encoded using simple array arithmetic.
3. Inserting into a Heap
Suppose we have a min-heap:
10
/ \
20 30
/ \
40 50
Now insert:
5
The new value is first placed at the next available position:
10
/ \
20 30
/ \ /
40 50 5
But this violates the heap property:
5 < 30
So 5 moves upward.
This process is called heapify-up, bubble-up, or sift-up.
Eventually:
5
/ \
20 10
/ \ /
40 50 30
The heap property has been restored.
For a binary heap:
Insertion → O(log n)
because the new element can move at most the height of the tree.
4. Removing the Root
Suppose we have:
5
/ \
20 10
/ \ / \
40 50 30
We want to remove the minimum value 5.
We typically move the last element to the root:
30
/ \
20 10
/ \
40 50
Now the heap property is broken:
30 > 10
So we move 30 downward.
This process is called heapify-down, bubble-down, or sift-down.
Result:
10
/ \
20 30
/ \
40 50
For a binary heap:
Remove root → O(log n)
5. Complexity
A typical binary heap provides:
| Operation | Complexity |
|---|---|
| Get minimum/maximum | O(1) |
| Insert | O(log n) |
| Remove minimum/maximum | O(log n) |
| Search arbitrary value | O(n) |
| Build heap | O(n) |
The important distinction is:
Root access → O(1)
Arbitrary search → O(n)
A heap is optimized for repeatedly getting the highest- or lowest-priority element, not for searching for arbitrary values.
6. Heapify
Heapify means restoring the heap property.
Suppose:
50
/ \
20 30
is supposed to be a min-heap.
The root violates the property because:
50 > 20
Heapify moves 50 downward:
20
/ \
50 30
and continues if necessary.
Heapify is one of the fundamental operations behind both heap insertion/removal and heap sort.
7. Heap Sort
A heap can also be used for sorting.
For a max-heap:
90
/ \
70 80
we repeatedly remove the maximum value.
Conceptually:
90 → 80 → 70 → ...
This gives Heap Sort, which has:
Time Complexity: O(n log n)
One interesting property of heap sort is that its worst-case time complexity remains:
O(n log n)
8. Priority Queues
A heap is one of the most common ways to implement a priority queue.
Remember the queue you learned earlier:
FIFO
A priority queue works differently.
Instead of:
First arrival → First processed
it uses:
Highest/lowest priority → First processed
A heap makes this efficient:
Priority Queue
↓
Heap
↓
Priority element at root
This is why heaps are so closely associated with scheduling and priority-based algorithms.
The Bigger Picture
Heaps connect several concepts you've already learned:
Trees
↓
Binary Trees
↓
Complete Binary Trees
↓
Heaps
↓
Priority Queues
They also connect to important algorithms:
Heap
├── Heap Sort
├── Dijkstra's Algorithm
├── Prim's Algorithm
└── Top-K Problems
For example, suppose you need the 10 largest numbers from a dataset containing millions of values.
Sorting everything would cost approximately:
O(n log n)
A heap can sometimes solve the problem more efficiently by maintaining only the relevant top k elements.
This is an example of an important algorithmic pattern:
Don't process or store more information than the problem requires.
The Most Important Mental Model
A heap keeps the most important element at the root while maintaining just enough order to make updates efficient.
For a min-heap:
MIN
↓
10
/ \
20 30
/ \ / \
40 50 60 70
For a max-heap:
MAX
↓
70
/ \
50 60
/ \ / \
20 40 10 30
Don't think:
"Everything is sorted."
Think:
"The root is guaranteed to be the minimum/maximum,
and every parent maintains the heap relationship
with its children."
That's the core idea.
Summary
A heap is a specialized complete binary tree designed to efficiently access the minimum or maximum element.
The key ideas are:
- A min-heap keeps the smallest element at the root.
- A max-heap keeps the largest element at the root.
- A heap is a complete binary tree.
- The heap is not completely sorted.
- A heap can be efficiently represented using an array.
- In a 0-based array, children of index
iare at2i + 1and2i + 2. - Insertion takes O(log n).
- Removing the root takes O(log n).
- Accessing the minimum or maximum takes O(1).
- Heaps are commonly used to implement priority queues.
- Heap sort runs in O(n log n).
- Heaps are important in algorithms such as Dijkstra's and Prim's algorithms.
Top comments (0)