From 64a6fd685b076de360b5a49594df1c70984ca6b0 Mon Sep 17 00:00:00 2001 From: Jeff Hemminger Date: Sat, 24 Jan 2026 14:40:43 +0900 Subject: [PATCH] refactored leftist heap implementation --- .gitignore | 1 + src/algorithms/heap/leftist_priority_heap.rs | 349 +++++++++++-------- 2 files changed, 204 insertions(+), 146 deletions(-) diff --git a/.gitignore b/.gitignore index ea8c4bf..6b39d31 100644 --- a/.gitignore +++ b/.gitignore @@ -1 +1,2 @@ /target +.idea/ \ No newline at end of file diff --git a/src/algorithms/heap/leftist_priority_heap.rs b/src/algorithms/heap/leftist_priority_heap.rs index d5de02e..116c606 100644 --- a/src/algorithms/heap/leftist_priority_heap.rs +++ b/src/algorithms/heap/leftist_priority_heap.rs @@ -1,14 +1,24 @@ 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. +/// A semigroup: a type with an associative combine operation +pub trait Semigroup { + fn combine(self, other: Self) -> Self; +} + +/// A monoid: a semigroup with an identity element +pub trait Monoid: Semigroup { + fn identity() -> Self; +} + +/// A persistent leftist heap implementing a priority queue. /// -/// Type parameters: -/// - `T`: The element type, must be `Ord` for heap ordering +/// Key properties: +/// - Heap property: every node ≤ its children (min-heap) +/// - Leftist property: rank(left) >= rank(right) at every node +/// - Rank = 1 + min(rank(left), rank(right)) (null path length) +/// +/// This ensures merge is O(log n), not O(n). #[derive(Clone, Debug)] pub enum Heap { Empty, @@ -21,18 +31,20 @@ pub enum Heap { } impl Heap { - /// Identity element of the heap monoid + /// Create an empty heap (identity element) pub fn empty() -> Self { Heap::Empty } - /// Check if the heap is empty (testing for identity) + /// Check if heap is empty 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 + /// Get the rank (null path length) of a heap. + /// Rank represents the shortest path to an empty node down the right spine. + /// For Empty: rank = 0 + /// For Node: rank = 1 + min(rank(left), rank(right)) fn rank(&self) -> usize { match self { Heap::Empty => 0, @@ -40,77 +52,97 @@ impl Heap { } } - /// Smart constructor maintaining the leftist property - /// This ensures our invariant through construction + /// Smart constructor: creates a node with elem, left, right, + /// and automatically maintains the leftist property by swapping children if needed. 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) + // Decide whether to swap children + let (left, right, rank) = if left_rank >= right_rank { + // Left rank is already >= right rank, keep as-is + (left, right, right_rank + 1) } else { - (right, left) + // Right rank is larger; swap them, and use left_rank for new rank + (right, left, left_rank + 1) }; Heap::Node { - rank: right_rank + 1, + rank, elem, left: Rc::new(left), right: Rc::new(right), } } + /// Try to unwrap an Rc: if we have the only reference, extract the heap for free. + /// If the heap is shared, clone it (necessary for persistence). 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 + /// Merge two heaps into one, maintaining heap and leftist properties. + /// This is the fundamental operation that makes leftist heaps efficient. + /// + /// Algorithm: + /// 1. If either heap is empty, return the other (identity) + /// 2. Compare roots; the smaller becomes the new root + /// 3. Recursively merge: the other root's subtree + the new root's right subtree + /// 4. Use make_node to rebuild, which auto-restores leftist property + /// + /// Time: O(log n) due to right spine being short (guaranteed by leftist property) pub fn merge(self, other: Self) -> Self { match (self, other) { - (Heap::Empty, h) => h, - (h, Heap::Empty) => h, + // Base cases: if either is empty, return the other + (Heap::Empty, h) | (h, Heap::Empty) => h, + + // Both non-empty: compare roots (h1, h2) => { + // Peek at roots without consuming to compare let is_h1_smaller = match (&h1, &h2) { - (Heap::Node { elem: x, .. }, Heap::Node { elem: y, .. }) => x <= y, + (Heap::Node { elem: e1, .. }, Heap::Node { elem: e2, .. }) => e1 <= e2, _ => unreachable!(), }; - // 1. The Isomorphism: Swap (h1, h2) -> (root, other) based on ordering - // This eliminates the branching logic by normalizing the data inputs. - let (root, other) = if is_h1_smaller { (h1, h2) } else { (h2, h1) }; - - // 2. Unify the Logic - if let Heap::Node { - elem, left, right, .. - } = root - { - let left_heap = Self::unwrap_or_clone(left); - let right_heap = Self::unwrap_or_clone(right); - - // 3. Currying / Partial Application - // We create a closure `node_builder` representing the function: Heap -> Heap - // It captures the fixed context (elem, left) and waits for the new right branch. - let node_builder = |new_right| Self::make_node(elem, left_heap, new_right); - - // 4. Evaluation - node_builder(right_heap.merge(other)) + if is_h1_smaller { + // h1 has the smaller root; merge h1.right with h2 + Self::merge_root(h1, h2) } else { - unreachable!() + // h2 has the smaller root; merge h2.right with h1 + Self::merge_root(h2, h1) } } } } - /// Insert: defined in terms of merge (following monoid composition) - /// insert(x, h) = merge(singleton(x), h) + /// Helper: assumes `root_heap` has the smaller root. + /// Merges root_heap.right with other_heap, keeping root_heap.elem and root_heap.left fixed. + fn merge_root(root_heap: Heap, other_heap: Heap) -> Self { + if let Heap::Node { + elem, + left, + right, + .. + } = root_heap + { + // Extract left and right children + // try_unwrap succeeds if we're the sole owner (cheap) + // if shared, clone is necessary to maintain persistence + let left_heap = Self::unwrap_or_clone(left); + let right_heap = Self::unwrap_or_clone(right); + + // Recursively merge the right subtree with the other heap + let merged_right = right_heap.merge(other_heap); + + // Rebuild the node; make_node handles leftist property maintenance + Self::make_node(elem, left_heap, merged_right) + } else { + unreachable!() + } + } + + /// Insert a single element by creating a singleton heap and merging. + /// This follows the monoid composition principle: insert = merge with singleton. pub fn insert(self, elem: T) -> Self { let singleton = Heap::Node { rank: 1, @@ -130,53 +162,24 @@ impl Heap { } } - /// Delete minimum: removes root and merges children - /// Returns new heap (persistent/immutable operation) + /// Delete the minimum element, returning it and the new heap. + /// Deletion: remove root, then merge its left and right subtrees. 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 left_heap = Self::unwrap_or_clone(left); + let right_heap = Self::unwrap_or_clone(right); 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 + /// Fold (catamorphism) over the heap, visiting all elements. + /// This is a tree traversal combined with an accumulation function. pub fn fold(self, init: B, f: F) -> B where F: Fn(B, T) -> B + Copy, @@ -186,13 +189,9 @@ impl Heap { 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) + let acc = f(init, elem); + let acc = Self::unwrap_or_clone(left).fold(acc, f); + Self::unwrap_or_clone(right).fold(acc, f) } } } @@ -220,6 +219,20 @@ impl Heap { } } +/// Implement Semigroup for Heap: merge is the combine operation +impl Semigroup for Heap { + fn combine(self, other: Self) -> Self { + self.merge(other) + } +} + +/// Implement Monoid for Heap: Empty is the identity +impl Monoid for Heap { + fn identity() -> Self { + Heap::empty() + } +} + /// Iterator implementation for consuming heap in sorted order pub struct HeapIter { heap: Heap, @@ -248,89 +261,133 @@ impl IntoIterator for Heap { } } -// 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(); + fn test_monoid_left_identity() { + // Monoid law: identity.combine(h) == h + let h = Heap::empty().insert(5).insert(3).insert(7); + let h_copy = h.clone(); - // Left identity: merge(empty, h) = h - assert_eq!( - Heap::empty().merge(heap.clone()).to_sorted_vec(), - heap_clone.clone().to_sorted_vec() - ); + let result = Heap::::identity().combine(h); + assert_eq!(result.to_sorted_vec(), h_copy.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_monoid_right_identity() { + // Monoid law: h.combine(identity) == h + let h = Heap::empty().insert(5).insert(3).insert(7); + let h_copy = h.clone(); + + let result = h.combine(Heap::identity()); + assert_eq!(result.to_sorted_vec(), h_copy.to_sorted_vec()); } #[test] - fn test_merge_associativity() { + fn test_semigroup_associativity() { + // Semigroup law: (h1.combine(h2)).combine(h3) == h1.combine(h2.combine(h3)) 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)); + let left_assoc = h1.clone().combine(h2.clone()).combine(h3.clone()); + let right_assoc = h1.combine(h2.combine(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]); + fn test_basic_merge() { + let h1 = Heap::empty().insert(2).insert(10).insert(8); + let h2 = Heap::empty().insert(5).insert(15).insert(20); + + let merged = h1.combine(h2); + assert_eq!( + merged.to_sorted_vec(), + vec![2, 5, 8, 10, 15, 20] + ); } #[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]); + fn test_find_min() { + let h = Heap::empty().insert(5).insert(3).insert(7).insert(1); + assert_eq!(h.find_min(), Some(&1)); } #[test] - fn test_fold_catamorphism() { - let heap = Heap::empty().insert(1).insert(2).insert(3).insert(4); + fn test_delete_min() { + let h = Heap::empty().insert(5).insert(3).insert(7).insert(1).insert(9); + + let (min1, h) = h.delete_min().unwrap(); + assert_eq!(min1, 1); - // Sum all elements via catamorphism - let sum = heap.fold(0, |acc, x| acc + x); - assert_eq!(sum, 10); + let (min2, h) = h.delete_min().unwrap(); + assert_eq!(min2, 3); + + let sorted = h.to_sorted_vec(); + assert_eq!(sorted, vec![5, 7, 9]); } #[test] - fn test_from_iter() { - let vec = vec![5, 2, 8, 1, 9, 3]; - let heap = Heap::from_iter(vec.clone()); + fn test_to_sorted_vec() { + let h = Heap::from_iter(vec![5, 2, 8, 1, 9, 3]); + assert_eq!(h.to_sorted_vec(), vec![1, 2, 3, 5, 8, 9]); + } - let mut sorted = vec; - sorted.sort(); + #[test] + fn test_persistence() { + // Persistent data structure: original unaffected by modifications + let h1 = Heap::empty().insert(5).insert(3); + let h2 = h1.clone().insert(7); + let h3 = h1.clone().insert(1); + + // h1 unchanged + assert_eq!(h1.to_sorted_vec(), vec![3, 5]); + // h2 is h1 + 7 + assert_eq!(h2.to_sorted_vec(), vec![3, 5, 7]); + // h3 is h1 + 1 + assert_eq!(h3.to_sorted_vec(), vec![1, 3, 5]); + } + + #[test] + fn test_fold() { + let h = Heap::from_iter(vec![1, 2, 3, 4, 5]); + let sum = h.fold(0, |acc, x| acc + x); + assert_eq!(sum, 15); + } + + #[test] + fn test_rank_property() { + // Verify that rank is computed correctly + // rank(node) = 1 + min(rank(left), rank(right)) + let h = Heap::empty().insert(5).insert(3).insert(7); - assert_eq!(heap.to_sorted_vec(), sorted); + // The exact structure depends on merge order, but rank should always be valid + match h { + Heap::Node { + rank, + left, + right, + .. + } => { + let left_rank = left.rank(); + let right_rank = right.rank(); + // Verify the rank formula + assert_eq!(rank, 1 + left_rank.min(right_rank)); + // Verify leftist property + assert!(left_rank >= right_rank); + } + Heap::Empty => panic!("Expected non-empty heap"), + } + } + + #[test] + fn test_iterator() { + let h = Heap::from_iter(vec![5, 2, 8, 1, 9, 3]); + let collected: Vec<_> = h.into_iter().collect(); + assert_eq!(collected, vec![1, 2, 3, 5, 8, 9]); } } -- 2.49.1