Heaps & Priority Queues
Introduction
Priority queues are fundamental data structures that allow us to efficiently manage elements based on their priority rather than their insertion order. Unlike regular queues that follow First-In-First-Out (FIFO) principles, priority queues serve elements with higher priority first, regardless of when they were added.
The most efficient implementation of a priority queue is through a data structure called a heap. Heaps provide logarithmic time complexity for insertion and removal operations while maintaining the priority ordering property.
What is a Heap?
A heap is a specialized tree-based data structure that satisfies the heap property:
Max Heap: For any given node, its value is greater than or equal to the values of its children
Min Heap: For any given node, its value is less than or equal to the values of its children
Key Properties of Heaps
Complete Binary Tree: All levels are filled except possibly the last level, which is filled from left to right
Heap Property: Parent nodes maintain a specific ordering relationship with their children
Efficient Array Representation: Can be stored in an array without pointers
Parent-Child Relationships in Array Representation
When a heap is stored in an array starting at index 0:
Parent of node at index
i:(i - 1) / 2Left child of node at index
i:2 * i + 1Right child of node at index
i:2 * i + 2
Implementing a Max Heap in Swift
Let’s implement a generic max heap that can work with any comparable type:
struct MaxHeap<T: Comparable> {
private var elements: [T] = []
var isEmpty: Bool {
return elements.isEmpty
}
var count: Int {
return elements.count
}
var peek: T? {
return elements.first
}
// MARK: - Helper Methods
private func parentIndex(of index: Int) -> Int {
return (index - 1) / 2
}
private func leftChildIndex(of index: Int) -> Int {
return 2 * index + 1
}
private func rightChildIndex(of index: Int) -> Int {
return 2 * index + 2
}
private func hasLeftChild(at index: Int) -> Bool {
return leftChildIndex(of: index) < count
}
private func hasRightChild(at index: Int) -> Bool {
return rightChildIndex(of: index) < count
}
private func hasParent(at index: Int) -> Bool {
return parentIndex(of: index) >= 0
}
private func leftChild(of index: Int) -> T {
return elements[leftChildIndex(of: index)]
}
private func rightChild(of index: Int) -> T {
return elements[rightChildIndex(of: index)]
}
private func parent(of index: Int) -> T {
return elements[parentIndex(of: index)]
}
// MARK: - Core Operations
mutating func insert(_ element: T) {
elements.append(element)
heapifyUp(from: count - 1)
}
mutating func extractMax() -> T? {
guard !isEmpty else { return nil }
let max = elements[0]
elements[0] = elements[count - 1]
elements.removeLast()
if !isEmpty {
heapifyDown(from: 0)
}
return max
}
// MARK: - Heapify Operations
private mutating func heapifyUp(from index: Int) {
var currentIndex = index
while hasParent(at: currentIndex) &&
parent(of: currentIndex) < elements[currentIndex] {
let parentIndex = self.parentIndex(of: currentIndex)
elements.swapAt(currentIndex, parentIndex)
currentIndex = parentIndex
}
}
private mutating func heapifyDown(from index: Int) {
var currentIndex = index
while hasLeftChild(at: currentIndex) {
var largestChildIndex = leftChildIndex(of: currentIndex)
if hasRightChild(at: currentIndex) &&
rightChild(of: currentIndex) > leftChild(of: currentIndex) {
largestChildIndex = rightChildIndex(of: currentIndex)
}
if elements[currentIndex] >= elements[largestChildIndex] {
break
}
elements.swapAt(currentIndex, largestChildIndex)
currentIndex = largestChildIndex
}
}
}
Implementing a Min Heap
For a min heap, we need to reverse the comparison logic:
struct MinHeap<T: Comparable> {
private var elements: [T] = []
var isEmpty: Bool {
return elements.isEmpty
}
var count: Int {
return elements.count
}
var peek: T? {
return elements.first
}
// Helper methods remain the same...
mutating func insert(_ element: T) {
elements.append(element)
heapifyUp(from: count - 1)
}
mutating func extractMin() -> T? {
guard !isEmpty else { return nil }
let min = elements[0]
elements[0] = elements[count - 1]
elements.removeLast()
if !isEmpty {
heapifyDown(from: 0)
}
return min
}
private mutating func heapifyUp(from index: Int) {
var currentIndex = index
while hasParent(at: currentIndex) &&
parent(of: currentIndex) > elements[currentIndex] {
let parentIndex = self.parentIndex(of: currentIndex)
elements.swapAt(currentIndex, parentIndex)
currentIndex = parentIndex
}
}
private mutating func heapifyDown(from index: Int) {
var currentIndex = index
while hasLeftChild(at: currentIndex) {
var smallestChildIndex = leftChildIndex(of: currentIndex)
if hasRightChild(at: currentIndex) &&
rightChild(of: currentIndex) < leftChild(of: currentIndex) {
smallestChildIndex = rightChildIndex(of: currentIndex)
}
if elements[currentIndex] <= elements[smallestChildIndex] {
break
}
elements.swapAt(currentIndex, smallestChildIndex)
currentIndex = smallestChildIndex
}
}
// Include the same helper methods as MaxHeap...
}
Generic Priority Queue Implementation
Let’s create a more flexible priority queue that can work as either a max heap or min heap:
enum HeapType {
case maxHeap
case minHeap
}
struct PriorityQueue<T: Comparable> {
private var elements: [T] = []
private let heapType: HeapType
init(type: HeapType = .maxHeap) {
self.heapType = type
}
var isEmpty: Bool {
return elements.isEmpty
}
var count: Int {
return elements.count
}
var peek: T? {
return elements.first
}
mutating func enqueue(_ element: T) {
elements.append(element)
heapifyUp(from: count - 1)
}
mutating func dequeue() -> T? {
guard !isEmpty else { return nil }
let priority = elements[0]
elements[0] = elements[count - 1]
elements.removeLast()
if !isEmpty {
heapifyDown(from: 0)
}
return priority
}
private func shouldSwapParent(_ parent: T, _ child: T) -> Bool {
switch heapType {
case .maxHeap:
return parent < child
case .minHeap:
return parent > child
}
}
private func shouldSwapChild(_ parent: T, _ child: T) -> Bool {
switch heapType {
case .maxHeap:
return parent < child
case .minHeap:
return parent > child
}
}
private func betterChild(_ left: T, _ right: T) -> T {
switch heapType {
case .maxHeap:
return left > right ? left : right
case .minHeap:
return left < right ? left : right
}
}
private mutating func heapifyUp(from index: Int) {
var currentIndex = index
while hasParent(at: currentIndex) &&
shouldSwapParent(parent(of: currentIndex), elements[currentIndex]) {
let parentIndex = self.parentIndex(of: currentIndex)
elements.swapAt(currentIndex, parentIndex)
currentIndex = parentIndex
}
}
private mutating func heapifyDown(from index: Int) {
var currentIndex = index
while hasLeftChild(at: currentIndex) {
var targetChildIndex = leftChildIndex(of: currentIndex)
if hasRightChild(at: currentIndex) {
let leftChild = self.leftChild(of: currentIndex)
let rightChild = self.rightChild(of: currentIndex)
if betterChild(leftChild, rightChild) == rightChild {
targetChildIndex = rightChildIndex(of: currentIndex)
}
}
if !shouldSwapChild(elements[currentIndex], elements[targetChildIndex]) {
break
}
elements.swapAt(currentIndex, targetChildIndex)
currentIndex = targetChildIndex
}
}
// Include the same helper methods...
}
Advanced Priority Queue with Custom Priorities
For more complex scenarios, we might want to use custom objects with explicit priorities:
struct PriorityItem<T> {
let item: T
let priority: Int
}
extension PriorityItem: Comparable {
static func < (lhs: PriorityItem<T>, rhs: PriorityItem<T>) -> Bool {
return lhs.priority < rhs.priority
}
static func == (lhs: PriorityItem<T>, rhs: PriorityItem<T>) -> Bool {
return lhs.priority == rhs.priority
}
}
struct CustomPriorityQueue<T> {
private var heap = PriorityQueue<PriorityItem<T>>(type: .maxHeap)
var isEmpty: Bool {
return heap.isEmpty
}
var count: Int {
return heap.count
}
mutating func enqueue(_ item: T, priority: Int) {
let priorityItem = PriorityItem(item: item, priority: priority)
heap.enqueue(priorityItem)
}
mutating func dequeue() -> T? {
return heap.dequeue()?.item
}
func peek() -> T? {
return heap.peek?.item
}
}
Time Complexity Analysis
Heap Operations
Operation |
Time Complexity |
Space Complexity |
|---|---|---|
Insert |
O(log n) |
O(1) |
Extract |
O(log n) |
O(1) |
Peek |
O(1) |
O(1) |
Build Heap |
O(n) |
O(n) |
Priority Queue Operations
Operation |
Time Complexity |
Space Complexity |
|---|---|---|
Enqueue |
O(log n) |
O(1) |
Dequeue |
O(log n) |
O(1) |
Peek |
O(1) |
O(1) |
Practical Applications
1. Task Scheduling System
struct Task {
let id: String
let name: String
let priority: Int
let deadline: Date
}
class TaskScheduler {
private var taskQueue = CustomPriorityQueue<Task>()
func addTask(_ task: Task) {
taskQueue.enqueue(task, priority: task.priority)
}
func getNextTask() -> Task? {
return taskQueue.dequeue()
}
func hasWaitingTasks() -> Bool {
return !taskQueue.isEmpty
}
}
2. Dijkstra’s Algorithm Implementation
struct Edge {
let destination: Int
let weight: Int
}
struct Graph {
private var adjacencyList: [Int: [Edge]] = [:]
mutating func addEdge(from source: Int, to destination: Int, weight: Int) {
adjacencyList[source, default: []].append(Edge(destination: destination, weight: weight))
}
func dijkstra(from start: Int, to end: Int) -> Int? {
var distances: [Int: Int] = [start: 0]
var priorityQueue = PriorityQueue<(node: Int, distance: Int)>(type: .minHeap)
var visited: Set<Int> = []
priorityQueue.enqueue((node: start, distance: 0))
while !priorityQueue.isEmpty {
guard let current = priorityQueue.dequeue() else { break }
if visited.contains(current.node) { continue }
visited.insert(current.node)
if current.node == end {
return current.distance
}
for edge in adjacencyList[current.node, default: []] {
let newDistance = current.distance + edge.weight
if newDistance < distances[edge.destination, default: Int.max] {
distances[edge.destination] = newDistance
priorityQueue.enqueue((node: edge.destination, distance: newDistance))
}
}
}
return nil
}
}
3. Huffman Coding Algorithm
class HuffmanNode {
let character: Character?
let frequency: Int
let left: HuffmanNode?
let right: HuffmanNode?
init(character: Character? = nil, frequency: Int, left: HuffmanNode? = nil, right: HuffmanNode? = nil) {
self.character = character
self.frequency = frequency
self.left = left
self.right = right
}
}
extension HuffmanNode: Comparable {
static func < (lhs: HuffmanNode, rhs: HuffmanNode) -> Bool {
return lhs.frequency < rhs.frequency
}
static func == (lhs: HuffmanNode, rhs: HuffmanNode) -> Bool {
return lhs.frequency == rhs.frequency
}
}
func buildHuffmanTree(from frequencies: [Character: Int]) -> HuffmanNode? {
var priorityQueue = PriorityQueue<HuffmanNode>(type: .minHeap)
// Create leaf nodes for each character
for (char, freq) in frequencies {
let node = HuffmanNode(character: char, frequency: freq)
priorityQueue.enqueue(node)
}
// Build the tree
while priorityQueue.count > 1 {
let left = priorityQueue.dequeue()!
let right = priorityQueue.dequeue()!
let merged = HuffmanNode(
frequency: left.frequency + right.frequency,
left: left,
right: right
)
priorityQueue.enqueue(merged)
}
return priorityQueue.dequeue()
}
Best Practices and Considerations
When to Use Heaps and Priority Queues
Task Scheduling: When you need to process items based on priority
Graph Algorithms: Dijkstra’s algorithm, Prim’s MST algorithm
Real-time Systems: Managing events by timestamp or priority
Data Compression: Huffman coding algorithm
Simulation Systems: Event-driven simulations
Performance Considerations
Memory Usage: Heaps use contiguous memory, providing good cache locality
Build Heap: If you have all elements upfront, building a heap in O(n) time is more efficient than n insertions
Stability: Heaps are not stable; equal elements might be reordered
Common Pitfalls
Index Calculations: Off-by-one errors in parent/child index calculations
Heap Property Violations: Forgetting to maintain heap property after modifications
Empty Heap Operations: Not checking for empty heap before peek/extract operations
Exercises
Exercise 1: Median Finder
Implement a data structure that can find the median of a stream of integers efficiently.
Exercise 2: Merge K Sorted Lists
Use a priority queue to merge k sorted linked lists into one sorted list.
Exercise 3: Top K Frequent Elements
Find the k most frequent elements in an array using a heap-based approach.
Exercise 4: Meeting Room Scheduler
Design a meeting room scheduler that can handle overlapping meetings using priority queues.
Summary
Heaps and priority queues are essential data structures for scenarios requiring efficient priority-based operations. The heap’s array-based implementation provides excellent performance characteristics while maintaining the flexibility to work with any comparable type.
Key takeaways:
Heaps maintain partial ordering through the heap property
Priority queues abstract the heap complexity for priority-based operations
Both structures provide O(log n) insertion and extraction with O(1) peek operations
They’re fundamental to many algorithms including Dijkstra’s, Huffman coding, and task scheduling
Understanding these data structures opens the door to solving complex algorithmic problems efficiently and building robust priority-based systems in Swift applications.