Heaps and Priority Queues

Introduction

In this lesson, we'll explore heaps and priority queues, their properties, and their usage in Rust. Heaps and priority queues are essential for managing and accessing data with priority.

Key Points

• Heaps: A specialized tree-based data structure that satisfies the heap property, commonly used to implement priority queues.
• Priority Queues: An abstract data type where each element has a priority, and elements are served based on their priority.

Heaps

A heap is a complete binary tree that satisfies the heap property. There are two types of heaps:

• Max-Heap: The value of each node is greater than or equal to the values of its children.
• Min-Heap: The value of each node is less than or equal to the values of its children.

Max-Heap Implementation

Here’s a basic implementation of a max-heap in Rust using a vector:

#[derive(Debug)]
struct MaxHeap<T> {
    heap: Vec<T>,
}

impl<T: Ord> MaxHeap<T> {
    fn new() -> Self {
        MaxHeap { heap: Vec::new() }
    }

    fn insert(&mut self, value: T) {
        self.heap.push(value);
        self.heapify_up(self.heap.len() - 1);
    }

    fn extract_max(&mut self) -> Option<T> {
        if self.heap.is_empty() {
            return None;
        }
        let max = self.heap.swap_remove(0);
        self.heapify_down(0);
        Some(max)
    }

    fn heapify_up(&mut self, index: usize) {
        let mut child = index;
        while child > 0 {
            let parent = (child - 1) / 2;
            if self.heap[child] <= self.heap[parent] {
                break;
            }
            self.heap.swap(child, parent);
            child = parent;
        }
    }

    fn heapify_down(&mut self, index: usize) {
        let mut parent = index;
        let len = self.heap.len();
        loop {
            let mut max = parent;
            let left = 2 * parent + 1;
            let right = 2 * parent + 2;

            if left < len && self.heap[left] > self.heap[max] {
                max = left;
            }
            if right < len && self.heap[right] > self.heap[max] {
                max = right;
            }
            if max == parent {
                break;
            }
            self.heap.swap(parent, max);
            parent = max;
        }
    }
}

fn main() {
    let mut max_heap = MaxHeap::new();
    max_heap.insert(10);
    max_heap.insert(20);
    max_heap.insert(5);

    println!("Max Heap: {:?}", max_heap);

    while let Some(max) = max_heap.extract_max() {
        println!("Extracted Max: {}", max);
    }
}

Code Explanation

• insert: Adds a value to the heap and maintains the heap property.
• extract_max: Removes and returns the maximum value from the heap.
• heapify_up: Reorders the heap after insertion to maintain the heap property.
• heapify_down: Reorders the heap after extraction to maintain the heap property.

Priority Queues

A priority queue is an abstract data type where each element has a priority. Elements are dequeued based on their priority rather than their order of insertion.

Priority Queue Implementation with Heap

Here's an implementation of a priority queue using a max-heap in Rust:

#[derive(Debug)]
struct PriorityQueue<T> {
    heap: MaxHeap<T>,
}

impl<T: Ord> PriorityQueue<T> {
    fn new() -> Self {
        PriorityQueue {
            heap: MaxHeap::new(),
        }
    }

    fn enqueue(&mut self, value: T) {
        self.heap.insert(value);
    }

    fn dequeue(&mut self) -> Option<T> {
        self.heap.extract_max()
    }

    fn peek(&self) -> Option<&T> {
        self.heap.heap.first()
    }
}

fn main() {
    let mut pq = PriorityQueue::new();
    pq.enqueue(30);
    pq.enqueue(10);
    pq.enqueue(20);

    println!("Priority Queue: {:?}", pq);

    while let Some(max) = pq.dequeue() {
        println!("Dequeued: {}", max);
    }
}

Code Explanation

• enqueue: Adds an element to the priority queue with the given priority.
• dequeue: Removes and returns the element with the highest priority.
• peek: Returns a reference to the element with the highest priority without removing it.

Real World Examples

Heaps

Heaps are often used in:

• Heap Sort: A sorting algorithm that uses a heap to sort elements efficiently.
• Task Scheduling: In operating systems, heaps can manage tasks based on their priority.

Priority Queues

Priority queues are used in scenarios where tasks or elements need to be processed based on priority:

• Dijkstra’s Algorithm: Used in shortest path algorithms where nodes are processed based on their distance.
• Job Scheduling: In operating systems, priority queues manage processes or tasks based on their priority.

Conclusion

Heaps and priority queues are powerful data structures for managing and accessing data with priority. By implementing these structures in Rust, you can handle various applications more efficiently and understand key algorithms better.