From 0761f45d68939872924dbacf5ad8d15765e7fa6b Mon Sep 17 00:00:00 2001 From: Jeff Hemminger Date: Wed, 24 Dec 2025 10:22:26 +0900 Subject: [PATCH] starting heap work --- src/algorithms/heap/leftist_priority_heap.rs | 337 +++++++++++++++++++ src/algorithms/heap/min_priority_heap.rs | 168 +++++++++ src/algorithms/heap/mod.rs | 5 + 3 files changed, 510 insertions(+) create mode 100644 src/algorithms/heap/leftist_priority_heap.rs create mode 100644 src/algorithms/heap/min_priority_heap.rs create mode 100644 src/algorithms/heap/mod.rs diff --git a/src/algorithms/heap/leftist_priority_heap.rs b/src/algorithms/heap/leftist_priority_heap.rs new file mode 100644 index 0000000..d31397e --- /dev/null +++ b/src/algorithms/heap/leftist_priority_heap.rs @@ -0,0 +1,337 @@ +use std::fmt::Debug; +use std::rc::Rc; + +/// A persistent leftist heap implementing a priority queue +/// with efficient merge operations and structural sharing. +/// A leftist heap merges at O(log n), versus O(n) for binary heaps. +/// It can do this because the leftist property keeps the right spine +/// short so merge only recurses logarithmically deep. +/// +/// Type parameters: +/// - `T`: The element type, must be `Ord` for heap ordering +#[derive(Clone, Debug)] +pub enum Heap { + Empty, + Node { + rank: usize, + elem: T, + left: Rc>, + right: Rc>, + }, +} + +impl Heap { + /// Identity element of the heap monoid + pub fn empty() -> Self { + Heap::Empty + } + + /// Check if the heap is empty (testing for identity) + pub fn is_empty(&self) -> bool { + matches!(self, Heap::Empty) + } + + /// Retrieve the rank (length of right spine) + /// This is a measure/annotation on our tree structure + fn rank(&self) -> usize { + match self { + Heap::Empty => 0, + Heap::Node { rank, .. } => *rank, + } + } + + /// Smart constructor maintaining the leftist property + /// This ensures our invariant through construction + fn make_node(elem: T, left: Heap, right: Heap) -> Self { + let left_rank = left.rank(); + let right_rank = right.rank(); + + // Maintain leftist property: left rank >= right rank + let (left, right) = if left_rank >= right_rank { + (left, right) + } else { + (right, left) + }; + + Heap::Node { + rank: right_rank + 1, + elem, + left: Rc::new(left), + right: Rc::new(right), + } + } + + fn unwrap_or_clone(rc: Rc) -> Self { + Rc::try_unwrap(rc).unwrap_or_else(|rc| (*rc).clone()) + } + + // Merge operation: the fundamental monoid operation + // This is associative: merge(merge(a, b), c) ≡ merge(a, merge(b, c)) + // Empty is identity: merge(Empty, h) ≡ merge(h, Empty) ≡ h + // Merge(h1, h2): + // 1. Compare roots: smaller becomes new root + // (this is where the magic happens) + // 2. Recursively: merge(new_root.right, other_heap) // ↓ right spine only! + // 3. If rank(left) < rank(right), swap children // restore leftist property + pub fn merge(self, other: Self) -> Self { + match (self, other) { + (Heap::Empty, h) => h, + (h, Heap::Empty) => h, + (h1, h2) => { + let is_h1_smaller = match (&h1, &h2) { + (Heap::Node { elem: x, .. }, Heap::Node { elem: y, .. }) => x <= y, + _ => unreachable!(), + }; + + if is_h1_smaller { + if let Heap::Node { + elem, left, right, .. + } = h1 + { + let left_heap = Self::unwrap_or_clone(left); + let right_heap = Self::unwrap_or_clone(right); + Self::make_node(elem, left_heap, right_heap.merge(h2)) + } else { + unreachable!() + } + } else { + if let Heap::Node { + elem, left, right, .. + } = h2 + { + let left_heap = Self::unwrap_or_clone(left); + let right_heap = Self::unwrap_or_clone(right); + Self::make_node(elem, left_heap, h1.merge(right_heap)) + } else { + unreachable!() + } + } + } + } + } + + /// Insert: defined in terms of merge (following monoid composition) + /// insert(x, h) = merge(singleton(x), h) + pub fn insert(self, elem: T) -> Self { + let singleton = Heap::Node { + rank: 1, + elem, + left: Rc::new(Heap::Empty), + right: Rc::new(Heap::Empty), + }; + self.merge(singleton) + } + + /// Find minimum element (root of heap) + /// This is a simple F-algebra: collapsing to optional value + pub fn find_min(&self) -> Option<&T> { + match self { + Heap::Empty => None, + Heap::Node { elem, .. } => Some(elem), + } + } + + /// Delete minimum: removes root and merges children + /// Returns new heap (persistent/immutable operation) + pub fn delete_min(self) -> Option<(T, Self)> { + match self { + Heap::Empty => None, + Heap::Node { + elem, left, right, .. + } => { + // Extract children from Rc + let left_heap = Rc::try_unwrap(left).unwrap_or_else(|rc| (*rc).clone()); + let right_heap = Rc::try_unwrap(right).unwrap_or_else(|rc| (*rc).clone()); + + // Merge children to form new heap + let new_heap = left_heap.merge(right_heap); + Some((elem, new_heap)) + } + } + } + + /// Functor-like map over heap structure + /// Note: This breaks heap property unless f preserves ordering! + /// Only use with order-preserving functions + pub fn map(self, f: F) -> Heap + where + U: Ord + Clone, + F: Fn(T) -> U + Copy, + { + match self { + Heap::Empty => Heap::Empty, + Heap::Node { + elem, left, right, .. + } => { + let mapped_elem = f(elem); + let mapped_left = Rc::try_unwrap(left) + .unwrap_or_else(|rc| (*rc).clone()) + .map(f); + let mapped_right = Rc::try_unwrap(right) + .unwrap_or_else(|rc| (*rc).clone()) + .map(f); + + Heap::make_node(mapped_elem, mapped_left, mapped_right) + } + } + } + + /// Catamorphism: fold the heap structure + /// This is the F-algebra approach to consuming heap structure + pub fn fold(self, init: B, f: F) -> B + where + F: Fn(B, T) -> B + Copy, + { + match self { + Heap::Empty => init, + Heap::Node { + elem, left, right, .. + } => { + let result = f(init, elem); + let result = Rc::try_unwrap(left) + .unwrap_or_else(|rc| (*rc).clone()) + .fold(result, f); + Rc::try_unwrap(right) + .unwrap_or_else(|rc| (*rc).clone()) + .fold(result, f) + } + } + } + + /// Build heap from iterator (using fold and merge) + pub fn from_iter(iter: I) -> Self + where + I: IntoIterator, + { + iter.into_iter() + .fold(Heap::empty(), |heap, elem| heap.insert(elem)) + } + + /// Convert to sorted vector (heap sort via repeated delete_min) + pub fn to_sorted_vec(self) -> Vec { + let mut result = Vec::new(); + let mut heap = self; + + while let Some((min, rest)) = heap.delete_min() { + result.push(min); + heap = rest; + } + + result + } +} + +/// Iterator implementation for consuming heap in sorted order +pub struct HeapIter { + heap: Heap, +} + +impl Iterator for HeapIter { + type Item = T; + + fn next(&mut self) -> Option { + match std::mem::replace(&mut self.heap, Heap::empty()).delete_min() { + Some((elem, rest)) => { + self.heap = rest; + Some(elem) + } + None => None, + } + } +} + +impl IntoIterator for Heap { + type Item = T; + type IntoIter = HeapIter; + + fn into_iter(self) -> Self::IntoIter { + HeapIter { heap: self } + } +} + +// Demonstrate monoid laws with property-based testing +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn test_empty_is_identity() { + let heap = Heap::empty().insert(5).insert(3).insert(7); + let heap_clone = heap.clone(); + + // Left identity: merge(empty, h) = h + assert_eq!( + Heap::empty().merge(heap.clone()).to_sorted_vec(), + heap_clone.clone().to_sorted_vec() + ); + + // Right identity: merge(h, empty) = h + assert_eq!( + heap_clone.clone().merge(Heap::empty()).to_sorted_vec(), + heap_clone.to_sorted_vec() + ); + } + + #[test] + fn test_merge_associativity() { + let h1 = Heap::empty().insert(1).insert(4); + let h2 = Heap::empty().insert(2).insert(5); + let h3 = Heap::empty().insert(3).insert(6); + + // (h1 ⊕ h2) ⊕ h3 + let left_assoc = h1.clone().merge(h2.clone()).merge(h3.clone()); + + // h1 ⊕ (h2 ⊕ h3) + let right_assoc = h1.merge(h2.merge(h3)); + + assert_eq!(left_assoc.to_sorted_vec(), right_assoc.to_sorted_vec()); + } + + #[test] + fn test_basic_operations() { + let heap = Heap::empty() + .insert(5) + .insert(3) + .insert(7) + .insert(1) + .insert(9); + + assert_eq!(heap.find_min(), Some(&1)); + + let sorted = heap.to_sorted_vec(); + assert_eq!(sorted, vec![1, 3, 5, 7, 9]); + } + + #[test] + fn test_persistence() { + let heap1 = Heap::empty().insert(5).insert(3); + let heap2 = heap1.clone().insert(7); + let heap3 = heap1.clone().insert(1); + + // Original heap unchanged + assert_eq!(heap1.to_sorted_vec(), vec![3, 5]); + // New versions have different elements + assert_eq!(heap2.to_sorted_vec(), vec![3, 5, 7]); + assert_eq!(heap3.to_sorted_vec(), vec![1, 3, 5]); + } + + #[test] + fn test_fold_catamorphism() { + let heap = Heap::empty().insert(1).insert(2).insert(3).insert(4); + + // Sum all elements via catamorphism + let sum = heap.fold(0, |acc, x| acc + x); + assert_eq!(sum, 10); + } + + #[test] + fn test_from_iter() { + let vec = vec![5, 2, 8, 1, 9, 3]; + let heap = Heap::from_iter(vec.clone()); + + let mut sorted = vec; + sorted.sort(); + + assert_eq!(heap.to_sorted_vec(), sorted); + } +} diff --git a/src/algorithms/heap/min_priority_heap.rs b/src/algorithms/heap/min_priority_heap.rs new file mode 100644 index 0000000..5c5a72e --- /dev/null +++ b/src/algorithms/heap/min_priority_heap.rs @@ -0,0 +1,168 @@ +/// A compact binary min-heap (complete binary tree in a Vec). +/// Functional/persistent API: many operations consume self and return a new heap. +/// Internals are vector-based for cache efficiency. +#[derive(Clone, Debug, PartialEq, Eq)] +pub struct BinaryHeap { + // Invariant: `data` is a complete binary tree stored level-order. + // Root at index 0. Parent of i is (i-1)/2. Children: 2*i+1, 2*i+2. + data: Vec, +} + +impl BinaryHeap { + /// Create an empty heap. + pub fn empty() -> Self { + Self { data: Vec::new() } + } + + /// Create a heap from an existing Vec (consumes vec). Does NOT heapify. + /// Use `from_vec_heapify` or `from_slice` to build a heap. + pub fn from_vec(vec: Vec) -> Self { + Self { data: vec } + } + + /// Number of elements. + pub fn len(&self) -> usize { + self.data.len() + } + + /// Is empty? + pub fn is_empty(&self) -> bool { + self.data.is_empty() + } + + /// Peek min without removing. + pub fn peek_min(&self) -> Option<&T> { + self.data.get(0) + } + + /// Pop the minimum, returning (min, new_heap). Consumes self (functional style). + pub fn pop_min(mut self) -> Option<(T, Self)> { + match self.data.len() { + 0 => None, + 1 => { + let v = self.data.pop().unwrap(); + Some((v, Self::empty())) + } + n => { + // swap root with last, pop last (old root), then sift-down new root + self.data.swap(0, n - 1); + let min = self.data.pop().unwrap(); + Self::sift_down_inplace(&mut self.data, 0); + Some((min, self)) + } + } + } + + /// Insert an element, returning a new heap (consumes self). + pub fn insert(mut self, item: T) -> Self { + let idx = self.data.len(); // immutable borrow ends here[1] + self.data.push(item); + Self::sift_up_inplace(&mut self.data, idx); // only mutable borrow now[1] + self + } + + /// Replace the root with `item`, return (old_root, new_heap). + /// Useful to do a pop then push more efficiently (heapreplace). + pub fn replace_root(mut self, item: T) -> Option<(Vec, Self)> { + if self.data.is_empty() { + // nothing to replace; equivalent to push + self.data.push(item); + None + } else { + let old = std::mem::replace(&mut self.data, vec![item]); + Self::sift_down_inplace(&mut self.data, 0); + Some((old, self)) + } + } + + /// Build a heap from an iterator (O(n log n) if inserting repeatedly). + /// Provided for completeness; prefer from_slice for O(n). + pub fn from_iter>(iter: I) -> Self { + iter.into_iter().fold(Self::empty(), |h, x| h.insert(x)) + } + + /// Heapify a Vec in-place (bottom-up) and return a heap. This is the O(n) algorithm. + /// This corresponds to the classical heapify/BUILD-MIN-HEAP algorithm. + pub fn from_vec_heapify(mut vec: Vec) -> Self { + if vec.len() <= 1 { + return Self { data: vec }; + } + let last_parent = (vec.len() - 2) / 2; // index of last internal node + for idx in (0..=last_parent).rev() { + Self::sift_down_inplace(&mut vec, idx); + } + Self { data: vec } + } + + /// Heapify a slice by cloning into an owned Vec and running bottom-up heapify. + pub fn from_slice(slice: &[T]) -> Self + where + T: Clone, + { + let v: Vec = slice.to_vec(); + Self::from_vec_heapify(v) + } + + // --- internal helpers (pure functions operating on Vec) --- + + /// Sift up element at `pos` (restore heap property by swapping with parent while < parent). + /// Invariants: `data` is a valid heap except possibly at `pos` which may be smaller than parent. + fn sift_up_inplace(data: &mut [T], mut pos: usize) { + while pos > 0 { + let parent = (pos - 1) / 2; + if data[pos] < data[parent] { + data.swap(pos, parent); + pos = parent; + } else { + break; + } + } + } + + /// Sift down element at `pos` (restore heap property by swapping with smaller child). + /// Invariants: `data` is a valid heap except possibly at `pos` which may be greater than children. + fn sift_down_inplace(data: &mut [T], mut pos: usize) { + let len = data.len(); + loop { + let left = 2 * pos + 1; + if left >= len { + break; + } + let right = left + 1; + // pick smaller child + let mut smallest = left; + if right < len && data[right] < data[left] { + smallest = right; + } + if data[smallest] < data[pos] { + data.swap(pos, smallest); + pos = smallest; + } else { + break; + } + } + } + + /// Expose the internal vector (consumes heap). + pub fn into_vec(self) -> Vec { + self.data + } + + /// Convert heap to a sorted Vec by repeatedly popping min (non-in-place heap sort). + /// Consumes the heap. + pub fn into_sorted_vec(mut self) -> Vec { + let mut out = Vec::with_capacity(self.len()); + while let Some((min, rest)) = self.pop_min() { + out.push(min); + self = rest; + } + out + } +} + +// Provide a small convenience: make a heap from a list literal +impl From> for BinaryHeap { + fn from(v: Vec) -> Self { + BinaryHeap::from_vec_heapify(v) + } +} diff --git a/src/algorithms/heap/mod.rs b/src/algorithms/heap/mod.rs new file mode 100644 index 0000000..04b84b1 --- /dev/null +++ b/src/algorithms/heap/mod.rs @@ -0,0 +1,5 @@ +pub mod leftist_priority_heap; +pub mod min_priority_heap; + +// pub use leftist_priority_heap::*; +// pub use min_priority_heap::*; -- 2.49.1