967 Advanced

967 Priority Queue

Functional Programming

Tutorial

The Problem

Implement a min-heap priority queue from scratch and compare it with Rust's standard BinaryHeap (max-heap). The manual min-heap uses sift-up on push and sift-down on pop. Also demonstrate the Reverse<T> wrapper pattern for converting the standard max-heap into a min-heap.

🎯 Learning Outcomes

• Implement MinHeap<T: Ord> using a Vec<T> with 0-indexed heap invariant

• Implement sift_up: while parent > current, swap and move up

• Implement sift_down: compare with both children, swap with smaller, repeat

• Use BinaryHeap::push(Reverse(x)) for a min-heap with the standard library

• Understand why BinaryHeap is a max-heap by default and when Reverse is appropriate

Code Example

#![allow(clippy::all)]
// 967: Priority Queue
// Approach 1: Manual min-heap implementation
// Approach 2: std::collections::BinaryHeap (max-heap, wrap for min)

// --- Approach 1: Manual min-heap ---
pub struct MinHeap<T: Ord> {
    data: Vec<T>,
}

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

    pub fn push(&mut self, x: T) {
        self.data.push(x);
        self.sift_up(self.data.len() - 1);
    }

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

    pub fn pop(&mut self) -> Option<T> {
        if self.data.is_empty() {
            return None;
        }
        let last = self.data.len() - 1;
        self.data.swap(0, last);
        let top = self.data.pop();
        if !self.data.is_empty() {
            self.sift_down(0);
        }
        top
    }

    pub fn size(&self) -> usize {
        self.data.len()
    }

    pub fn is_empty(&self) -> bool {
        self.data.is_empty()
    }

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

    fn sift_down(&mut self, mut i: usize) {
        loop {
            let left = 2 * i + 1;
            let right = 2 * i + 2;
            let mut smallest = i;
            if left < self.data.len() && self.data[left] < self.data[smallest] {
                smallest = left;
            }
            if right < self.data.len() && self.data[right] < self.data[smallest] {
                smallest = right;
            }
            if smallest != i {
                self.data.swap(i, smallest);
                i = smallest;
            } else {
                break;
            }
        }
    }
}

impl<T: Ord> Default for MinHeap<T> {
    fn default() -> Self {
        Self::new()
    }
}

// --- Approach 2: std BinaryHeap (max-heap; use Reverse for min-heap) ---
use std::cmp::Reverse;
use std::collections::BinaryHeap;

pub fn heap_sort(mut values: Vec<i32>) -> Vec<i32> {
    let mut heap: BinaryHeap<Reverse<i32>> = BinaryHeap::new();
    for v in values.drain(..) {
        heap.push(Reverse(v));
    }
    let mut sorted = Vec::with_capacity(heap.len());
    while let Some(Reverse(v)) = heap.pop() {
        sorted.push(v);
    }
    sorted
}

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

    #[test]
    fn test_min_heap_order() {
        let mut h: MinHeap<i32> = MinHeap::new();
        h.push(5);
        h.push(3);
        h.push(8);
        h.push(1);
        h.push(9);
        h.push(2);

        assert_eq!(h.peek(), Some(&1));
        assert_eq!(h.size(), 6);
        assert_eq!(h.pop(), Some(1));
        assert_eq!(h.pop(), Some(2));
        assert_eq!(h.pop(), Some(3));
        assert_eq!(h.pop(), Some(5));
        assert_eq!(h.pop(), Some(8));
        assert_eq!(h.pop(), Some(9));
        assert_eq!(h.pop(), None);
    }

    #[test]
    fn test_heap_sort_manual() {
        let mut h: MinHeap<i32> = MinHeap::new();
        for v in [4, 7, 2, 1, 8, 3, 6, 5] {
            h.push(v);
        }
        let mut sorted = vec![];
        while let Some(v) = h.pop() {
            sorted.push(v);
        }
        assert_eq!(sorted, vec![1, 2, 3, 4, 5, 6, 7, 8]);
    }

    #[test]
    fn test_std_binary_heap_min() {
        let sorted = heap_sort(vec![4, 7, 2, 1, 8, 3, 6, 5]);
        assert_eq!(sorted, vec![1, 2, 3, 4, 5, 6, 7, 8]);
    }

    #[test]
    fn test_empty() {
        let mut h: MinHeap<i32> = MinHeap::new();
        assert!(h.is_empty());
        assert_eq!(h.peek(), None);
        assert_eq!(h.pop(), None);
    }

    #[test]
    fn test_single() {
        let mut h: MinHeap<i32> = MinHeap::new();
        h.push(42);
        assert_eq!(h.peek(), Some(&42));
        assert_eq!(h.size(), 1);
        assert_eq!(h.pop(), Some(42));
        assert!(h.is_empty());
    }
}

(* 967: Priority Queue (Min-Heap from scratch) *)
(* Binary heap: parent <= children (min-heap) *)

type 'a heap = {
  mutable data: 'a array;
  mutable size: int;
  compare: 'a -> 'a -> int;
}

let create ?(capacity=16) compare =
  { data = Array.make capacity (Obj.magic 0);
    size = 0;
    compare }

let swap h i j =
  let tmp = h.data.(i) in
  h.data.(i) <- h.data.(j);
  h.data.(j) <- tmp

let sift_up h i =
  let i = ref i in
  while !i > 0 do
    let parent = (!i - 1) / 2 in
    if h.compare h.data.(!i) h.data.(parent) < 0 then begin
      swap h !i parent;
      i := parent
    end else
      i := 0  (* break *)
  done

let sift_down h i =
  let i = ref i in
  let continue_ = ref true in
  while !continue_ do
    let left = 2 * !i + 1 in
    let right = 2 * !i + 2 in
    let smallest = ref !i in
    if left < h.size && h.compare h.data.(left) h.data.(!smallest) < 0 then
      smallest := left;
    if right < h.size && h.compare h.data.(right) h.data.(!smallest) < 0 then
      smallest := right;
    if !smallest <> !i then begin
      swap h !i !smallest;
      i := !smallest
    end else
      continue_ := false
  done

let push h x =
  if h.size = Array.length h.data then begin
    let new_data = Array.make (h.size * 2) (Obj.magic 0) in
    Array.blit h.data 0 new_data 0 h.size;
    h.data <- new_data
  end;
  h.data.(h.size) <- x;
  h.size <- h.size + 1;
  sift_up h (h.size - 1)

let peek h =
  if h.size = 0 then None
  else Some h.data.(0)

let pop h =
  if h.size = 0 then None
  else begin
    let top = h.data.(0) in
    h.size <- h.size - 1;
    if h.size > 0 then begin
      h.data.(0) <- h.data.(h.size);
      sift_down h 0
    end;
    Some top
  end

let size h = h.size

let () =
  let h = create compare in
  push h 5;
  push h 3;
  push h 8;
  push h 1;
  push h 9;
  push h 2;

  assert (peek h = Some 1);
  assert (size h = 6);

  assert (pop h = Some 1);
  assert (pop h = Some 2);
  assert (pop h = Some 3);
  assert (pop h = Some 5);
  assert (pop h = Some 8);
  assert (pop h = Some 9);
  assert (pop h = None);

  (* Heap sort test *)
  let h2 = create compare in
  List.iter (push h2) [4; 7; 2; 1; 8; 3; 6; 5];
  let sorted = ref [] in
  while size h2 > 0 do
    sorted := (pop h2 |> Option.get) :: !sorted
  done;
  assert (List.rev !sorted = [1;2;3;4;5;6;7;8]);

  Printf.printf "✓ All tests passed\n"

Key Differences

Aspect	Rust	OCaml
Standard PQ	`BinaryHeap` (max-heap)	No built-in; `Set.Make` for unique elements
Min-heap standard	`Reverse<T>` wrapper	`Set.Make` with reversed compare
Array access	`self.data[i]`	`h.data.(i)`
Index arithmetic	Same 0-indexed formula	Same

OCaml Approach

(* OCaml stdlib: module Heap does not exist; use a sorted list or custom *)
(* Simple min-heap as an array *)
let create () = { data = Array.make 64 0; size = 0 }

let parent i = (i - 1) / 2
let left i = 2 * i + 1
let right i = 2 * i + 2

let swap h i j =
  let tmp = h.data.(i) in
  h.data.(i) <- h.data.(j);
  h.data.(j) <- tmp

let rec sift_up h i =
  if i > 0 && h.data.(i) < h.data.(parent i) then begin
    swap h i (parent i);
    sift_up h (parent i)
  end

(* Standard library alternative *)
(* module PQ = Set.Make(Int) — sorted set acts like priority queue *)

OCaml's standard library has Set.Make(M) which provides O(log n) add and min/max removal — equivalent to a priority queue but without duplicate support. For duplicates, Map.Make(Int) with count values works.

Full Source

#![allow(clippy::all)]
// 967: Priority Queue
// Approach 1: Manual min-heap implementation
// Approach 2: std::collections::BinaryHeap (max-heap, wrap for min)

// --- Approach 1: Manual min-heap ---
pub struct MinHeap<T: Ord> {
    data: Vec<T>,
}

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

    pub fn push(&mut self, x: T) {
        self.data.push(x);
        self.sift_up(self.data.len() - 1);
    }

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

    pub fn pop(&mut self) -> Option<T> {
        if self.data.is_empty() {
            return None;
        }
        let last = self.data.len() - 1;
        self.data.swap(0, last);
        let top = self.data.pop();
        if !self.data.is_empty() {
            self.sift_down(0);
        }
        top
    }

    pub fn size(&self) -> usize {
        self.data.len()
    }

    pub fn is_empty(&self) -> bool {
        self.data.is_empty()
    }

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

    fn sift_down(&mut self, mut i: usize) {
        loop {
            let left = 2 * i + 1;
            let right = 2 * i + 2;
            let mut smallest = i;
            if left < self.data.len() && self.data[left] < self.data[smallest] {
                smallest = left;
            }
            if right < self.data.len() && self.data[right] < self.data[smallest] {
                smallest = right;
            }
            if smallest != i {
                self.data.swap(i, smallest);
                i = smallest;
            } else {
                break;
            }
        }
    }
}

impl<T: Ord> Default for MinHeap<T> {
    fn default() -> Self {
        Self::new()
    }
}

// --- Approach 2: std BinaryHeap (max-heap; use Reverse for min-heap) ---
use std::cmp::Reverse;
use std::collections::BinaryHeap;

pub fn heap_sort(mut values: Vec<i32>) -> Vec<i32> {
    let mut heap: BinaryHeap<Reverse<i32>> = BinaryHeap::new();
    for v in values.drain(..) {
        heap.push(Reverse(v));
    }
    let mut sorted = Vec::with_capacity(heap.len());
    while let Some(Reverse(v)) = heap.pop() {
        sorted.push(v);
    }
    sorted
}

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

    #[test]
    fn test_min_heap_order() {
        let mut h: MinHeap<i32> = MinHeap::new();
        h.push(5);
        h.push(3);
        h.push(8);
        h.push(1);
        h.push(9);
        h.push(2);

        assert_eq!(h.peek(), Some(&1));
        assert_eq!(h.size(), 6);
        assert_eq!(h.pop(), Some(1));
        assert_eq!(h.pop(), Some(2));
        assert_eq!(h.pop(), Some(3));
        assert_eq!(h.pop(), Some(5));
        assert_eq!(h.pop(), Some(8));
        assert_eq!(h.pop(), Some(9));
        assert_eq!(h.pop(), None);
    }

    #[test]
    fn test_heap_sort_manual() {
        let mut h: MinHeap<i32> = MinHeap::new();
        for v in [4, 7, 2, 1, 8, 3, 6, 5] {
            h.push(v);
        }
        let mut sorted = vec![];
        while let Some(v) = h.pop() {
            sorted.push(v);
        }
        assert_eq!(sorted, vec![1, 2, 3, 4, 5, 6, 7, 8]);
    }

    #[test]
    fn test_std_binary_heap_min() {
        let sorted = heap_sort(vec![4, 7, 2, 1, 8, 3, 6, 5]);
        assert_eq!(sorted, vec![1, 2, 3, 4, 5, 6, 7, 8]);
    }

    #[test]
    fn test_empty() {
        let mut h: MinHeap<i32> = MinHeap::new();
        assert!(h.is_empty());
        assert_eq!(h.peek(), None);
        assert_eq!(h.pop(), None);
    }

    #[test]
    fn test_single() {
        let mut h: MinHeap<i32> = MinHeap::new();
        h.push(42);
        assert_eq!(h.peek(), Some(&42));
        assert_eq!(h.size(), 1);
        assert_eq!(h.pop(), Some(42));
        assert!(h.is_empty());
    }
}

(* 967: Priority Queue (Min-Heap from scratch) *)
(* Binary heap: parent <= children (min-heap) *)

type 'a heap = {
  mutable data: 'a array;
  mutable size: int;
  compare: 'a -> 'a -> int;
}

let create ?(capacity=16) compare =
  { data = Array.make capacity (Obj.magic 0);
    size = 0;
    compare }

let swap h i j =
  let tmp = h.data.(i) in
  h.data.(i) <- h.data.(j);
  h.data.(j) <- tmp

let sift_up h i =
  let i = ref i in
  while !i > 0 do
    let parent = (!i - 1) / 2 in
    if h.compare h.data.(!i) h.data.(parent) < 0 then begin
      swap h !i parent;
      i := parent
    end else
      i := 0  (* break *)
  done

let sift_down h i =
  let i = ref i in
  let continue_ = ref true in
  while !continue_ do
    let left = 2 * !i + 1 in
    let right = 2 * !i + 2 in
    let smallest = ref !i in
    if left < h.size && h.compare h.data.(left) h.data.(!smallest) < 0 then
      smallest := left;
    if right < h.size && h.compare h.data.(right) h.data.(!smallest) < 0 then
      smallest := right;
    if !smallest <> !i then begin
      swap h !i !smallest;
      i := !smallest
    end else
      continue_ := false
  done

let push h x =
  if h.size = Array.length h.data then begin
    let new_data = Array.make (h.size * 2) (Obj.magic 0) in
    Array.blit h.data 0 new_data 0 h.size;
    h.data <- new_data
  end;
  h.data.(h.size) <- x;
  h.size <- h.size + 1;
  sift_up h (h.size - 1)

let peek h =
  if h.size = 0 then None
  else Some h.data.(0)

let pop h =
  if h.size = 0 then None
  else begin
    let top = h.data.(0) in
    h.size <- h.size - 1;
    if h.size > 0 then begin
      h.data.(0) <- h.data.(h.size);
      sift_down h 0
    end;
    Some top
  end

let size h = h.size

let () =
  let h = create compare in
  push h 5;
  push h 3;
  push h 8;
  push h 1;
  push h 9;
  push h 2;

  assert (peek h = Some 1);
  assert (size h = 6);

  assert (pop h = Some 1);
  assert (pop h = Some 2);
  assert (pop h = Some 3);
  assert (pop h = Some 5);
  assert (pop h = Some 8);
  assert (pop h = Some 9);
  assert (pop h = None);

  (* Heap sort test *)
  let h2 = create compare in
  List.iter (push h2) [4; 7; 2; 1; 8; 3; 6; 5];
  let sorted = ref [] in
  while size h2 > 0 do
    sorted := (pop h2 |> Option.get) :: !sorted
  done;
  assert (List.rev !sorted = [1;2;3;4;5;6;7;8]);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_min_heap_order() {
        let mut h: MinHeap<i32> = MinHeap::new();
        h.push(5);
        h.push(3);
        h.push(8);
        h.push(1);
        h.push(9);
        h.push(2);

        assert_eq!(h.peek(), Some(&1));
        assert_eq!(h.size(), 6);
        assert_eq!(h.pop(), Some(1));
        assert_eq!(h.pop(), Some(2));
        assert_eq!(h.pop(), Some(3));
        assert_eq!(h.pop(), Some(5));
        assert_eq!(h.pop(), Some(8));
        assert_eq!(h.pop(), Some(9));
        assert_eq!(h.pop(), None);
    }

    #[test]
    fn test_heap_sort_manual() {
        let mut h: MinHeap<i32> = MinHeap::new();
        for v in [4, 7, 2, 1, 8, 3, 6, 5] {
            h.push(v);
        }
        let mut sorted = vec![];
        while let Some(v) = h.pop() {
            sorted.push(v);
        }
        assert_eq!(sorted, vec![1, 2, 3, 4, 5, 6, 7, 8]);
    }

    #[test]
    fn test_std_binary_heap_min() {
        let sorted = heap_sort(vec![4, 7, 2, 1, 8, 3, 6, 5]);
        assert_eq!(sorted, vec![1, 2, 3, 4, 5, 6, 7, 8]);
    }

    #[test]
    fn test_empty() {
        let mut h: MinHeap<i32> = MinHeap::new();
        assert!(h.is_empty());
        assert_eq!(h.peek(), None);
        assert_eq!(h.pop(), None);
    }

    #[test]
    fn test_single() {
        let mut h: MinHeap<i32> = MinHeap::new();
        h.push(42);
        assert_eq!(h.peek(), Some(&42));
        assert_eq!(h.size(), 1);
        assert_eq!(h.pop(), Some(42));
        assert!(h.is_empty());
    }
}

Deep Comparison

Priority Queue — Comparison

Core Insight

A binary heap stores elements in array positions such that data[i] <= data[2i+1] and data[i] <= data[2i+2] (min-heap). Push appends and sifts up; pop swaps root with last, removes last, and sifts down. Both languages implement this identically. Rust also ships BinaryHeap (max-heap) in std; Reverse<T> flips ordering for min-heap use.

OCaml Approach

• Generic via compare: 'a -> 'a -> int higher-order function

• Obj.magic 0 initializes array slots (unsafe placeholder)

• Mutable record with mutable data and mutable size

• Array resizing via Array.blit when capacity exceeded

• sift_up/sift_down with ref for mutable loop index

Rust Approach

• Generic via T: Ord trait bound (compiler-enforced ordering)

• Vec<T> grows automatically — no manual resize needed

• data.swap(i, j) for in-place swap

• data.first() for peek; data.pop() for removal (O(1))

• Separate MinHeap<T> struct and std::collections::BinaryHeap with Reverse<T>

Comparison Table

Aspect	OCaml	Rust
Generics	`compare: 'a -> 'a -> int` arg	`T: Ord` trait bound
Storage	`'a array` (fixed, manually resized)	`Vec<T>` (auto-growing)
Initialize	`Obj.magic 0` (placeholder)	`Vec::new()` (empty)
Swap	Manual via tmp variable	`data.swap(i, j)`
Peek	`Some data.(0)`	`data.first()`
Pop remove	Manual `data.(h.size)`	`data.pop()` (Vec O(1))
Sift index	`ref i` in while loop	`let mut i` in loop
Std heap	n/a	`BinaryHeap<T>` (max) + `Reverse<T>`

Exercises

Implement heapify(vec: Vec<T>) -> MinHeap<T> that builds the heap in O(n) using Floyd's algorithm (sift-down from n/2-1 to 0).

Implement heap sort: build a max-heap, repeatedly pop to produce sorted output.

Use BinaryHeap<Reverse<(i32, usize)>> to implement Dijkstra's shortest path algorithm.

Implement decrease_key — update the priority of an existing element without removing and re-inserting.

Implement a k-way merge using a min-heap: merge k sorted arrays into one sorted array in O(n log k).

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust