//! }
//! }
//!
-//! fn main() {
-//! let mut heap = IndexdMinHeap::new(3);
-//! heap.push(State { node: 0, distance: 42 });
-//! heap.push(State { node: 1, distance: 23 });
-//! heap.push(State { node: 2, distance: 50000 });
-//! assert_eq!(heap.peek().cloned(), Some(State { node: 1, distance: 23 }));
-//! heap.decrease_key(State { node: 0, distance: 1 });
-//! assert_eq!(heap.pop(), Some(State { node: 0, distance: 1 }));
-//! }
+//! let mut heap = IndexdMinHeap::new(3);
+//! heap.push(State { node: 0, distance: 42 });
+//! heap.push(State { node: 1, distance: 23 });
+//! heap.push(State { node: 2, distance: 50000 });
+//! assert_eq!(heap.peek().cloned(), Some(State { node: 1, distance: 23 }));
+//! heap.decrease_key(State { node: 0, distance: 1 });
+//! assert_eq!(heap.pop(), Some(State { node: 0, distance: 1 }));
//!
//! ```
#[derive(Debug)]
pub struct IndexdMinHeap<T: Ord + Indexing> {
positions: Vec<usize>,
- data: Vec<T>
+ data: Vec<T>,
}
const TREE_ARITY: usize = 4;
pub fn new(max_index: usize) -> IndexdMinHeap<T> {
IndexdMinHeap {
positions: vec![INVALID_POSITION; max_index],
- data: Vec::new()
+ data: Vec::new(),
}
}
}
/// Updates the key of an element if the new key is smaller than the old key.
- /// Does nothing if the new key is larger.
- /// Panics if the element is not part of the queue.
+ /// Panics if the element is not part of the queue or if the new key is larger.
pub fn decrease_key(&mut self, element: T) {
let position = self.positions[element.as_index()];
+ assert!(element <= self.data[position]);
self.data[position] = element;
self.move_up_in_tree(position);
}
/// Updates the key of an element if the new key is larger than the old key.
- /// Does nothing if the new key is smaller.
- /// Panics if the element is not part of the queue.
+ /// Panics if the element is not part of the queue or if the new key is smaller.
pub fn increase_key(&mut self, element: T) {
let position = self.positions[element.as_index()];
+ assert!(element >= self.data[position]);
self.data[position] = element;
self.move_down_in_tree(position);
}
}
}
-
// This is an optimization copied straight from the rust stdlib binary heap
// it allows to avoid always swapping elements pairwise and rather
// move each element only once.
-
/// Hole represents a hole in a slice i.e. an index without valid value
/// (because it was moved from or duplicated).
/// In drop, `Hole` will restore the slice by filling the hole
unsafe fn new(data: &'a mut [T], pos: usize) -> Self {
debug_assert!(pos < data.len());
let elt = ptr::read(&data[pos]);
- Hole {
- data,
- elt: Some(elt),
- pos,
- }
+ Hole { data, elt: Some(elt), pos }
}
/// Returns a reference to the element removed.