Heaps & Priority Queues

A heap is a specialized tree-based data structure that maintains a strict ordering property while remaining perfectly balanced. Unlike binary search trees, heaps are optimized for fast access to the minimum or maximum element, not for searching arbitrary values.

Heaps are most commonly used to implement priority queues, where elements are processed based on priority rather than insertion order.

Heap Property

A binary heap is a complete binary tree that satisfies one of the following properties:

Min-Heap

• The value at each node is less than or equal to its children
• The minimum element is always at the root

Max-Heap

• The value at each node is greater than or equal to its children
• The maximum element is always at the root

Example (Min-Heap):

        1
       / \
      3   5
     / \ /
    4  6 8

This property guarantees fast access to the highest-priority element.

Complete Binary Tree Requirement

Heaps are always complete binary trees, meaning:

• All levels are fully filled except possibly the last
• The last level is filled from left to right

Because of this property, heaps are typically stored using arrays, not pointer-based trees.

Array Representation

For a heap stored in an array:

This allows efficient traversal without explicit node pointers.

Basic Operations

A binary heap supports three core operations:

1. Insert
2. Peek (min/max)
3. Extract (remove min/max)

These operations form the foundation of a priority queue.

Inserting into a Heap

Insertion works as follows:

1. Add the new element to the end of the array

2. Heapify up (bubble up):

   • Compare the element with its parent
   • Swap if the heap property is violated

3. Continue until the property is restored

This ensures the heap remains complete and ordered.

Removing from a Heap (Extract-Min / Extract-Max)

Removal follows these steps:

1. Remove the root element (min or max)

2. Move the last element to the root

3. Heapify down:

   • Compare with children
   • Swap with the appropriate child

4. Continue until the heap property is restored

Rust Implementation (Min-Heap)

Below is a clean, idiomatic min-heap implementation using a Vec<T>.

#[derive(Debug)]
pub struct MinHeap<T> {
    data: Vec<T>,
}

impl<T: Ord> MinHeap<T> {
    pub fn new() -> Self {
        MinHeap { data: Vec::new() }
    }

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

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

    pub fn extract_min(&mut self) -> Option<T> {
        if self.data.is_empty() {
            return None;
        }

        let last = self.data.pop().unwrap();
        if self.data.is_empty() {
            return Some(last);
        }

        let min = std::mem::replace(&mut self.data[0], last);
        self.heapify_down(0);
        Some(min)
    }

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

    fn heapify_down(&mut self, mut index: usize) {
        let len = self.data.len();

        loop {
            let left = 2 * index + 1;
            let right = 2 * index + 2;
            let mut smallest = index;

            if left < len && self.data[left] < self.data[smallest] {
                smallest = left;
            }

            if right < len && self.data[right] < self.data[smallest] {
                smallest = right;
            }

            if smallest == index {
                break;
            }

            self.data.swap(index, smallest);
            index = smallest;
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn it_orders_elements() {
        let mut heap = MinHeap::new();
        heap.insert(5);
        heap.insert(3);
        heap.insert(8);
        heap.insert(1);

        assert_eq!(heap.extract_min(), Some(1));
        assert_eq!(heap.extract_min(), Some(3));
        assert_eq!(heap.extract_min(), Some(5));
        assert_eq!(heap.extract_min(), Some(8));
    }
}

Example Usage

fn main() {
    let mut heap = MinHeap::new();

    for v in [5, 3, 8, 1, 6] {
        heap.insert(v);
    }

    while let Some(min) = heap.extract_min() {
        println!("{}", min);
    }
}

Output:

1
3
5
6
8

Priority Queue Concept

A priority queue is an abstract data type where:

• Each element has a priority
• The highest-priority element is processed first

Heaps are the most efficient and common way to implement priority queues.

Time and Space Complexity

Time Complexity

Space Complexity

Limitations of Heaps

• No efficient search for arbitrary elements
• No ordering traversal like BSTs
• Only guarantees access to min or max

Heaps trade ordering flexibility for priority efficiency.

Playground Links

Rust - Min Heap & Priority Queue