Introduction
A heap is a special type of tree that always keeps the biggest (or smallest) value at the top. Think of it like a stack of plates where the largest (or smallest) plate is always on top.
There are two main types:
Max Heap → The biggest number is always at the top.
Min Heap → The smallest number is always at the top.
Heaps are great when we need to quickly find the largest or smallest value in a set of numbers. Instead of searching through everything, we can get the top value instantly!
Real-World Uses of a Heap
Priority Queue → Imagine a hospital where critical patients get treated first. A heap helps keep track of which patient should be next.
Dijkstra’s Algorithm → This is used in Google Maps to find the shortest route from one place to another.
Task Scheduling → Computers use heaps to decide which program should run next, based on priority.
What is a Heap?
A heap is a type of complete binary tree, which means:
- Every level of the tree is completely filled, except possibly the last level.
- The last level fills from left to right without skipping any spots.
Heap property examples
This is the example of Max and Min heap:
Heap Operations
Heapify: Ensuring the Heap Property
Heapify is used to fix the heap property after insertion or deletion.
Heapify-up (bubble up): Used after insertion.
Heapify-down (bubble down): Used after deletion.
We will use this property in the examples below.
Insertion: Maintaining the Heap Property
When adding a new element to a heap, we always insert it at the next available position to keep the tree complete. But this might break the heap property (the biggest/smallest number must be at the top). To fix this, we move the new value upward using heapify.
Step 1: Insert the new element at the next available position (to keep the tree complete).
Step 2: Move the element upward (heapify-up) if it violates the heap property.
Max Heap → Swap with parent if it's larger than the parent.
Min Heap → Swap with parent if it's smaller than the parent.
Example (Max Heap - Insert 40)
Current Max heap:
- Insert 40 at the next available position.
- Swap 40 with 15, and then swap 40 with 30. (Heapify-up until it doens't violate heap property.)
Heap property is restored.
Deletion (Extract Max/Min): Removing the Root and Restructuring
To remove the root:
Step 1: Replace the root with the last element.
Step 2: Move the new root downward (heapify-down) if needed to restore order.
Max Heap → Swap with the largest child if it's smaller than a child.
Min Heap → Swap with the smallest child if it's larger than a child.
Example (Max Heap - Remove 50)
Current Max heap:
- Remove 50 and move 15 to the root.
- Swap 15 with 40, and then swap 15 and 30 to restore order.
Heap property is restored.
Implementing a Heap in Java
Check out pros and cons between array-based vs tree-based.
The array-based approach is the most common and efficient.
Here is Java cod implementation for a basic Max Heap:
class MaxHeap {
private int[] heap;
private int size;
private int capacity;
public MaxHeap(int capacity) {
this.capacity = capacity;
heap = new int[capacity];
size = 0;
}
private int parent(int i) { return (i - 1) / 2; }
private int leftChild(int i) { return 2 * i + 1; }
private int rightChild(int i) { return 2 * i + 2; }
public void insert(int value) {
if (size == capacity) throw new IllegalStateException("Heap is full");
heap[size] = value;
int current = size;
size++;
while (current > 0 && heap[current] > heap[parent(current)]) {
swap(current, parent(current));
current = parent(current);
}
}
public int extractMax() {
if (size == 0) throw new IllegalStateException("Heap is empty");
int max = heap[0];
heap[0] = heap[size - 1];
size--;
heapify(0);
return max;
}
private void heapify(int i) {
int largest = i;
int left = leftChild(i);
int right = rightChild(i);
if (left < size && heap[left] > heap[largest]) largest = left;
if (right < size && heap[right] > heap[largest]) largest = right;
if (largest != i) {
swap(i, largest);
heapify(largest);
}
}
private void swap(int i, int j) {
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
}
Min heap:
class MinHeap {
private int[] heap;
private int size;
private int capacity;
public MinHeap(int capacity) {
this.capacity = capacity;
heap = new int[capacity];
size = 0;
}
private int parent(int i) { return (i - 1) / 2; }
private int leftChild(int i) { return 2 * i + 1; }
private int rightChild(int i) { return 2 * i + 2; }
public void insert(int value) {
if (size == capacity) throw new IllegalStateException("Heap is full");
heap[size] = value;
int current = size;
size++;
while (current > 0 && heap[current] < heap[parent(current)]) { // MinHeap 조건
swap(current, parent(current));
current = parent(current);
}
}
public int extractMin() {
if (size == 0) throw new IllegalStateException("Heap is empty");
int min = heap[0];
heap[0] = heap[size - 1];
size--;
heapify(0);
return min;
}
private void heapify(int i) {
int smallest = i;
int left = leftChild(i);
int right = rightChild(i);
if (left < size && heap[left] < heap[smallest]) smallest = left;
if (right < size && heap[right] < heap[smallest]) smallest = right;
if (smallest != i) {
swap(i, smallest);
heapify(smallest);
}
}
private void swap(int i, int j) {
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
}
Applications of Heaps
Heaps are widely used in various applications due to their efficient priority-based operations. One of the most common uses is priority queues, where elements are processed based on their priority rather than their insertion order. (e.g. Max heap and min heap) Another important application is Dijkstra’s Algorithm, which finds the shortest path in a graph. A min-heap is used to always expand the node with the smallest tentative distance, significantly optimizing the algorithm’s performance. Additionally, heaps play a crucial role in task scheduling, where jobs with higher priority are executed first. Operating systems and real-time applications often utilize heaps to manage CPU scheduling, ensuring that urgent tasks are handled promptly. Due to their logarithmic time complexity for insertion and deletion, heaps are an essential data structure for efficiently managing priority-based tasks.