Heaps & Priority Queues
Heaps and priority queues are specialized data structures that efficiently maintain the minimum or maximum element in a collection, enabling fast access to the highest or lowest priority element.
Module Contents
Introduction to Heaps
A heap is a specialized tree-based data structure that satisfies the heap property. The heap property varies depending on the type of heap:
Max Heap:
For every node i, the value of i is greater than or equal to the values of its children. The maximum element is always at the root.
Min Heap:
For every node i, the value of i is less than or equal to the values of its children. The minimum element is always at the root.
Key Properties of Heaps
- Complete Binary Tree: A heap is a complete binary tree, which means all levels are fully filled except possibly the last level, which is filled from left to right.
- Efficient Access: O(1) access to the maximum (in max heap) or minimum (in min heap) element.
- Efficient Insertion and Deletion: O(log n) time complexity for insertion and deletion operations.
- Array Representation: Heaps can be efficiently represented using arrays, without requiring explicit pointers.
- No Ordering Between Siblings: Unlike binary search trees, there is no specific ordering between siblings in a heap.
Array Representation of Heaps
A binary heap can be represented as an array where:
- The root element is at index 0 (or 1, depending on the implementation)
- For any element at index i:
- Its left child is at index 2i + 1 (or 2i if starting from 1)
- Its right child is at index 2i + 2 (or 2i + 1 if starting from 1)
- Its parent is at index ⌊(i-1)/2⌋ (or ⌊i/2⌋ if starting from 1)
Visual Representation:
10
/ \
9 8
/ \ / \
7 6 5 4Array representation: [10, 9, 8, 7, 6, 5, 4]
Binary Heap Implementation
Let's look at how to implement a binary heap data structure from scratch. We'll implement a min heap, but the same principles apply to a max heap with slight modifications.
Min Heap Implementation
public class MinHeap {
private int[] heap;
private int size;
private int capacity;
public MinHeap(int capacity) {
this.capacity = capacity;
this.size = 0;
this.heap = new int[capacity];
}
// Helper methods to get parent, left child, and right child indices
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;
}
// Swap two elements in the heap
private void swap(int i, int j) {
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
// Insert a new element into the heap
public void insert(int key) {
if (size == capacity) {
throw new IllegalStateException("Heap is full");
}
// Insert the new key at the end
int i = size;
heap[i] = key;
size++;
// Fix the min heap property if it is violated
// (Bubble up the newly inserted element)
while (i != 0 && heap[parent(i)] > heap[i]) {
swap(i, parent(i));
i = parent(i);
}
}
// Extract the minimum element from the heap
public int extractMin() {
if (size <= 0) {
throw new IllegalStateException("Heap is empty");
}
if (size == 1) {
size--;
return heap[0];
}
// Store the minimum value and remove it from the heap
int root = heap[0];
heap[0] = heap[size - 1];
size--;
// Restore the heap property (Heapify)
minHeapify(0);
return root;
}
// Heapify the subtree rooted at index i
private void minHeapify(int i) {
int left = leftChild(i);
int right = rightChild(i);
int smallest = i;
// Find the smallest among the node and its children
if (left < size && heap[left] < heap[smallest]) {
smallest = left;
}
if (right < size && heap[right] < heap[smallest]) {
smallest = right;
}
// If the smallest is not the current node, swap and continue heapifying
if (smallest != i) {
swap(i, smallest);
minHeapify(smallest);
}
}
// Get the minimum element without removing it
public int getMin() {
if (size <= 0) {
throw new IllegalStateException("Heap is empty");
}
return heap[0];
}
// Check if the heap is empty
public boolean isEmpty() {
return size == 0;
}
// Get the current size of the heap
public int size() {
return size;
}
// Print the heap
public void printHeap() {
for (int i = 0; i < size; i++) {
System.out.print(heap[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
MinHeap minHeap = new MinHeap(10);
minHeap.insert(3);
minHeap.insert(2);
minHeap.insert(1);
minHeap.insert(15);
minHeap.insert(5);
minHeap.insert(4);
minHeap.insert(45);
System.out.println("Heap: ");
minHeap.printHeap();
System.out.println("Min element: " + minHeap.getMin());
System.out.println("Extracting min: " + minHeap.extractMin());
System.out.println("Heap after extraction: ");
minHeap.printHeap();
}
}Max Heap Implementation
A max heap can be implemented similarly to a min heap, with the key difference being that the parent node is always greater than or equal to its children.
Key Differences from Min Heap:
- In the
insertmethod, we bubble up if the parent is smaller than the child - In the
heapifymethod, we look for the largest element instead of the smallest - The root element is the maximum value in the heap
Building a Heap from an Array
We can build a heap from an existing array in O(n) time by starting from the last non-leaf node and heapifying down to the root.
def build_max_heap(arr):
n = len(arr)
# Start from the last non-leaf node and heapify each node
for i in range(n // 2 - 1, -1, -1):
max_heapify(arr, n, i)
return arr
def max_heapify(arr, n, i):
largest = i # Initialize largest as root
left = 2 * i + 1
right = 2 * i + 2
# Check if left child exists and is greater than root
if left < n and arr[left] > arr[largest]:
largest = left
# Check if right child exists and is greater than largest so far
if right < n and arr[right] > arr[largest]:
largest = right
# If largest is not root
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] # Swap
# Recursively heapify the affected sub-tree
max_heapify(arr, n, largest)
# Example usage
arr = [4, 10, 3, 5, 1]
build_max_heap(arr)
print("Max Heap:", arr) # Output: [10, 5, 3, 4, 1]Priority Queue
A priority queue is an abstract data type that operates similar to a regular queue but with each element having a priority. Elements with higher priority are dequeued before elements with lower priority.
Priority Queue Operations
- insert(item, priority): Insert an item with the given priority
- extractMax()/extractMin(): Remove and return the highest/lowest priority element
- peek(): Return the highest/lowest priority element without removing it
- changePriority(item, priority): Change the priority of an item
- remove(item): Remove a specific item from the priority queue
Implementing Priority Queue using Heap
A binary heap is an efficient implementation of a priority queue. Here's how to implement a priority queue using a max heap:
class PriorityQueueItem {
int value;
int priority;
public PriorityQueueItem(int value, int priority) {
this.value = value;
this.priority = priority;
}
}
public class PriorityQueue {
private PriorityQueueItem[] heap;
private int size;
private int capacity;
public PriorityQueue(int capacity) {
this.capacity = capacity;
this.size = 0;
this.heap = new PriorityQueueItem[capacity];
}
// Helper methods
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;
}
private void swap(int i, int j) {
PriorityQueueItem temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
// Insert an item with a given priority
public void insert(int value, int priority) {
if (size == capacity) {
throw new IllegalStateException("Priority queue is full");
}
// Create a new item
PriorityQueueItem item = new PriorityQueueItem(value, priority);
// Insert at the end
int i = size;
heap[i] = item;
size++;
// Fix the max heap property (higher priority at the top)
while (i != 0 && heap[parent(i)].priority < heap[i].priority) {
swap(i, parent(i));
i = parent(i);
}
}
// Extract the highest priority item
public PriorityQueueItem extractMax() {
if (size <= 0) {
throw new IllegalStateException("Priority queue is empty");
}
if (size == 1) {
size--;
return heap[0];
}
// Store the highest priority item
PriorityQueueItem root = heap[0];
// Replace the root with the last item
heap[0] = heap[size - 1];
size--;
// Restore the heap property
maxHeapify(0);
return root;
}
// Heapify the subtree rooted at index i
private void maxHeapify(int i) {
int left = leftChild(i);
int right = rightChild(i);
int highest = i;
if (left < size && heap[left].priority > heap[highest].priority) {
highest = left;
}
if (right < size && heap[right].priority > heap[highest].priority) {
highest = right;
}
if (highest != i) {
swap(i, highest);
maxHeapify(highest);
}
}
// Get the highest priority item without removing it
public PriorityQueueItem peek() {
if (size <= 0) {
throw new IllegalStateException("Priority queue is empty");
}
return heap[0];
}
// Check if the priority queue is empty
public boolean isEmpty() {
return size == 0;
}
// Get the current size of the priority queue
public int size() {
return size;
}
public static void main(String[] args) {
PriorityQueue pq = new PriorityQueue(10);
pq.insert(10, 2);
pq.insert(20, 1);
pq.insert(30, 3);
pq.insert(40, 5);
pq.insert(50, 4);
System.out.println("Highest priority item: " + pq.peek().value);
while (!pq.isEmpty()) {
PriorityQueueItem item = pq.extractMax();
System.out.println("Item: " + item.value + ", Priority: " + item.priority);
}
}
}Using Java's PriorityQueue
Java provides a built-in PriorityQueue class that can be used with custom comparators:
import java.util.PriorityQueue;
import java.util.Comparator;
public class PriorityQueueExample {
static class Task {
String name;
int priority;
public Task(String name, int priority) {
this.name = name;
this.priority = priority;
}
@Override
public String toString() {
return name + " (Priority: " + priority + ")";
}
}
public static void main(String[] args) {
// Create a priority queue with a custom comparator (higher priority first)
PriorityQueue<Task> pq = new PriorityQueue<>(
Comparator.comparingInt((Task task) -> task.priority).reversed()
);
// Add tasks to the queue
pq.add(new Task("Task 1", 2));
pq.add(new Task("Task 2", 1));
pq.add(new Task("Task 3", 3));
pq.add(new Task("Task 4", 5));
pq.add(new Task("Task 5", 4));
// Process tasks in order of priority
System.out.println("Processing tasks in order of priority:");
while (!pq.isEmpty()) {
Task task = pq.poll();
System.out.println("Processing: " + task);
}
}
}Heap Operations
Let's explore the key operations on heaps and their time complexities.
Basic Heap Operations
| Operation | Description | Time Complexity |
|---|---|---|
| getMin/getMax | Get the minimum/maximum element | O(1) |
| extractMin/extractMax | Remove and return the minimum/maximum element | O(log n) |
| insert | Insert a new element into the heap | O(log n) |
| delete | Delete an element at a given index | O(log n) |
| decreaseKey/increaseKey | Decrease/increase the key of an element | O(log n) |
| buildHeap | Build a heap from an array | O(n) |
Heapify Operation
Heapify is a process of creating a heap from a binary tree. It is used in operations like extractMin/extractMax and buildHeap.
Heapify Process:
- Start with a node at index i
- Find the largest/smallest among the node and its children
- If the largest/smallest is not the current node, swap them
- Recursively heapify the affected subtree
Decrease Key and Increase Key
These operations are used to change the priority of an element in the heap.
// Decrease key operation for min heap
public void decreaseKey(int i, int newValue) {
if (newValue > heap[i]) {
throw new IllegalArgumentException("New value is greater than current value");
}
heap[i] = newValue;
// Fix the min heap property if it is violated
while (i != 0 && heap[parent(i)] > heap[i]) {
swap(i, parent(i));
i = parent(i);
}
}
// Increase key operation for max heap
public void increaseKey(int i, int newValue) {
if (newValue < heap[i]) {
throw new IllegalArgumentException("New value is less than current value");
}
heap[i] = newValue;
// Fix the max heap property if it is violated
while (i != 0 && heap[parent(i)] < heap[i]) {
swap(i, parent(i));
i = parent(i);
}
}Delete Operation
Deleting an element at a specific index involves replacing it with the last element and then heapifying.
// Delete operation for min heap
public void delete(int i) {
if (i >= size) {
throw new IllegalArgumentException("Index out of bounds");
}
// Decrease the key to the minimum possible value
decreaseKey(i, Integer.MIN_VALUE);
// Extract the minimum element (which is now at the root)
extractMin();
}Applications of Heaps and Priority Queues
Heaps and priority queues are used in various algorithms and applications due to their efficient operations.
1. Heap Sort
Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It has O(n log n) time complexity in all cases.
Heap Sort Algorithm:
- Build a max heap from the input array
- Swap the root (maximum element) with the last element of the heap
- Reduce the heap size by 1 and heapify the root
- Repeat steps 2 and 3 until the heap is empty
2. Dijkstra's Algorithm
Dijkstra's algorithm uses a priority queue to find the shortest path in a graph from a single source vertex to all other vertices.
Role of Priority Queue:
The priority queue is used to select the vertex with the smallest distance from the source. This ensures that vertices are processed in order of their distance from the source, leading to the correct shortest path.
3. Prim's Algorithm
Prim's algorithm uses a priority queue to find the minimum spanning tree of a connected, undirected graph.
Role of Priority Queue:
The priority queue is used to select the edge with the minimum weight that connects a vertex in the MST to a vertex outside the MST.
4. Huffman Coding
Huffman coding uses a priority queue to build an optimal prefix tree for data compression.
Role of Priority Queue:
The priority queue is used to select the two nodes with the lowest frequency to merge them into a new node. This process continues until a single tree is formed.
5. K-th Largest/Smallest Element
Finding the k-th largest or smallest element in an array can be efficiently done using a heap.
def find_kth_largest(nums, k):
# Use a min heap of size k
min_heap = []
for num in nums:
# If the heap size is less than k, add the element
if len(min_heap) < k:
heapq.heappush(min_heap, num)
# If the current element is larger than the smallest element in the heap,
# remove the smallest and add the current element
elif num > min_heap[0]:
heapq.heappop(min_heap)
heapq.heappush(min_heap, num)
# The root of the heap is the kth largest element
return min_heap[0]
# Example usage
nums = [3, 2, 1, 5, 6, 4]
k = 2
print(find_kth_largest(nums, k)) # Output: 56. Median of a Stream
Finding the median of a stream of numbers can be efficiently done using two heaps: a max heap for the lower half and a min heap for the upper half.
import java.util.PriorityQueue;
import java.util.Collections;
public class MedianFinder {
// Max heap for the lower half
private PriorityQueue<Integer> lowerHalf;
// Min heap for the upper half
private PriorityQueue<Integer> upperHalf;
public MedianFinder() {
lowerHalf = new PriorityQueue<>(Collections.reverseOrder());
upperHalf = new PriorityQueue<>();
}
public void addNum(int num) {
// Add to the appropriate heap
if (lowerHalf.isEmpty() || num <= lowerHalf.peek()) {
lowerHalf.add(num);
} else {
upperHalf.add(num);
}
// Balance the heaps
if (lowerHalf.size() > upperHalf.size() + 1) {
upperHalf.add(lowerHalf.poll());
} else if (upperHalf.size() > lowerHalf.size()) {
lowerHalf.add(upperHalf.poll());
}
}
public double findMedian() {
if (lowerHalf.size() == upperHalf.size()) {
// Even number of elements, average the two middle elements
return (lowerHalf.peek() + upperHalf.peek()) / 2.0;
} else {
// Odd number of elements, return the middle element
return lowerHalf.peek();
}
}
public static void main(String[] args) {
MedianFinder mf = new MedianFinder();
mf.addNum(1);
System.out.println("Median: " + mf.findMedian()); // Output: 1.0
mf.addNum(2);
System.out.println("Median: " + mf.findMedian()); // Output: 1.5
mf.addNum(3);
System.out.println("Median: " + mf.findMedian()); // Output: 2.0
}
}Advanced Heap Structures
Beyond binary heaps, there are several advanced heap data structures with different properties and performance characteristics.
1. Binomial Heap
A binomial heap is a collection of binomial trees, where each binomial tree has a specific structure and follows the heap property.
Key Properties:
- Supports efficient merging of two heaps in O(log n) time
- Operations like insert, extractMin, and decreaseKey have O(log n) amortized time complexity
- Useful in applications where merging heaps is a common operation
2. Fibonacci Heap
A Fibonacci heap is a collection of trees with min-heap or max-heap property, designed to improve the amortized time complexity of operations.
Key Properties:
- Supports O(1) amortized time for insert, decreaseKey, and merge operations
- extractMin operation has O(log n) amortized time complexity
- Used in optimized implementations of graph algorithms like Dijkstra's and Prim's
- More complex to implement than binary heaps
3. Leftist Heap
A leftist heap is a binary tree that satisfies the heap property and the leftist property, which ensures that the right path from any node to a leaf is the shortest path.
Key Properties:
- Supports efficient merging of two heaps in O(log n) time
- All operations have O(log n) worst-case time complexity
- Simpler to implement than Fibonacci heaps
- Useful in applications requiring frequent merge operations
4. Skew Heap
A skew heap is a self-adjusting binary heap that does not impose structural constraints but maintains balance through a specific merging operation.
Key Properties:
- Simpler to implement than leftist heaps
- All operations have O(log n) amortized time complexity
- No need to maintain any balance information
- Efficient for merging operations
Practice Problems
Test your understanding of heaps and priority queues with these practice problems.
1. Kth Largest Element in an Array
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
2. Merge K Sorted Lists
Merge k sorted linked lists and return it as one sorted list.
3. Find Median from Data Stream
Design a data structure that supports adding new numbers and finding the median of the current numbers.
4. Top K Frequent Elements
Given a non-empty array of integers, return the k most frequent elements.
5. Sliding Window Maximum
Given an array nums and a sliding window of size k, find the maximum element in each window as the window slides from left to right.