05
Priority Queues and Heaps
Chapter 5 • Intermediate
120 min
Priority Queues and Heaps
Priority Queue
A priority queue is a data structure where elements are served based on priority rather than insertion order.
Operations
- Insert: Add element with priority
- Extract-Max/Min: Remove highest/lowest priority element
- Peek: View highest/lowest priority element
- Update Priority: Change priority of existing element
Binary Heap
A binary heap is a complete binary tree that satisfies the heap property.
Heap Property
- Max Heap: Parent ≥ children
- Min Heap: Parent ≤ children
Array Representation
For node at index i:
- Parent: (i-1)/2
- Left child: 2i + 1
- Right child: 2i + 2
Max Heap Implementation
python.js
class MaxHeap:
def __init__(self):
self.heap = []
def parent(self, i):
return (i - 1) // 2
def left_child(self, i):
return 2 * i + 1
def right_child(self, i):
return 2 * i + 2
def swap(self, i, j):
self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
def insert(self, key):
self.heap.append(key)
self._heapify_up(len(self.heap) - 1)
def _heapify_up(self, i):
while i > 0 and self.heap[self.parent(i)] < self.heap[i]:
self.swap(i, self.parent(i))
i = self.parent(i)
def extract_max(self):
if not self.heap:
raise IndexError("Heap is empty")
if len(self.heap) == 1:
return self.heap.pop()
max_val = self.heap[0]
self.heap[0] = self.heap.pop()
self._heapify_down(0)
return max_val
def _heapify_down(self, i):
largest = i
left = self.left_child(i)
right = self.right_child(i)
if left < len(self.heap) and self.heap[left] > self.heap[largest]:
largest = left
if right < len(self.heap) and self.heap[right] > self.heap[largest]:
largest = right
if largest != i:
self.swap(i, largest)
self._heapify_down(largest)
def peek(self):
if not self.heap:
raise IndexError("Heap is empty")
return self.heap[0]
Time Complexities
| Operation | Time Complexity |
|---|---|
| Insert | O(log n) |
| Extract-Max/Min | O(log n) |
| Peek | O(1) |
| Build Heap | O(n) |
| Heapify | O(log n) |
Building a Heap
Building a heap from an array can be done in O(n) time using bottom-up approach.
python.js
def build_heap(arr):
"""Build max heap from array in O(n) time"""
n = len(arr)
# Start from last non-leaf node
for i in range(n // 2 - 1, -1, -1):
heapify_down(arr, n, i)
def heapify_down(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify_down(arr, n, largest)
Heap Sort
Heap sort uses a heap to sort an array.
Algorithm
- Build max heap from array
- Repeatedly extract max and place at end
- Reduce heap size and heapify
python.js
def heap_sort(arr):
n = len(arr)
# Build max heap
build_heap(arr)
# Extract elements one by one
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0] # Move max to end
heapify_down(arr, i, 0) # Heapify reduced heap
return arr
Time Complexity: O(n log n)
Space Complexity: O(1)
Applications
- Dijkstra's Algorithm: Find shortest paths
- Prim's Algorithm: Minimum spanning tree
- Huffman Coding: Data compression
- Task Scheduling: Priority-based scheduling
- Merge K Sorted Lists: Efficient merging
- Find K Largest Elements: O(n log k) solution
Priority Queue with Custom Priorities
python.js
import heapq
class PriorityQueue:
def __init__(self):
self.heap = []
self.count = 0 # For tie-breaking
def push(self, item, priority):
heapq.heappush(self.heap, (priority, self.count, item))
self.count += 1
def pop(self):
return heapq.heappop(self.heap)[2]
def is_empty(self):
return len(self.heap) == 0
Practice Problems
- Implement min heap from scratch
- Find K largest elements using heap
- Merge K sorted arrays using heap
- Implement heap sort
- Design a priority queue with update operation
- Find median using two heaps