mut_binary_heap/lib.rs
1#![allow(clippy::needless_doctest_main)]
2//! This crate provides [`BinaryHeap`] that stores key-value pairs.
3//! The main advantage of that is that unlike with an implementation like
4//! [`std::collections::BinaryHeap`] checking if any given key exist is `O(1)` instead of `O(n)`.
5//! Same for getting the value for a given key. This allows for cheap modification of
6//! values within the binary heap. Updating a value is `O(log n)` iff you have direct access to the value.
7//! For a binary heap that does not store key-value pairs update operations would be `O(n)` because
8//! they first have to find the value to update. The disadvantage is the additional storage space
9//! required to store a HashMap that provides indices into the heap for each key.
10//!
11//! # Quick start
12//!
13//! ## Max/Min Heap
14//!
15//! ### Max Heap
16//!
17//! ```rust
18//! use mut_binary_heap::*;
19//!
20//! // max heap
21//! let mut h: BinaryHeap<i32, i32> = BinaryHeap::new();
22//! // max heap with initial capacity
23//! let mut h: BinaryHeap<i32, i32> = BinaryHeap::with_capacity(42);
24//! // max heap from iterator and key selector
25//! let mut h: BinaryHeap<i32, i32> = BinaryHeap::from((0..42), |v| *v);
26//! assert_eq!(h.pop(), Some(41));
27//! ```
28//!
29//! ### Min Heap
30//!
31//! ```rust
32//! use mut_binary_heap::*;
33//!
34//! // min heap
35//! let mut h: BinaryHeap<i32, i32, MinComparator> = BinaryHeap::new();
36//! // min heap with initial capacity
37//! let mut h: BinaryHeap<i32, i32, MinComparator> = BinaryHeap::with_capacity(42);
38//! // min heap from iterator
39//! let mut h: BinaryHeap<i32, i32, MinComparator> = BinaryHeap::from((0..42), |v| *v);
40//! assert_eq!(h.pop(), Some(0));
41//! ```
42//!
43//! [`BinaryHeap::from_vec()`]: struct.BinaryHeap.html#method.from_vec
44//!
45//! ## Custom Heap
46//!
47//! For custom heap, [`BinaryHeap::new_by()`] and [`BinaryHeap::new_by_sort_key`]
48//! works in a similar way to max/min heap. The only difference is that you add
49//! a closure returning a [`std::cmp::Ordering`] or the sort key with an apropriate signature.
50//!
51//! ```rust
52//! use mut_binary_heap::BinaryHeap;
53//!
54//! let mut heap = BinaryHeap::new_by_sort_key(|a: &i32| a % 4);
55//! heap.push(0, 3);
56//! heap.push(1, 1);
57//! heap.push(2, 5);
58//! assert_eq!(heap.pop(), Some(3));
59//! ```
60//!
61//! # Constructers
62//!
63//! ## Dedicated methods to create different kind of heaps
64//!
65//! * [`BinaryHeap::new()`] creates a max heap.
66//! * [`BinaryHeap::new_min()`] creates a min heap.
67//! * [`BinaryHeap::new_by()`] creates a heap sorted by the given closure.
68//! * [`BinaryHeap::new_by_sort_key()`] creates a heap sorted by the key generated by the given closure.
69//! * [`BinaryHeap::from()`] creates a max heap with the elements in the iterator and keys provided by the closure.
70// TODO create BinaryHeap::from for min and custom heaps
71//!
72//! # Examples
73//!
74//! This is a larger example that implements [Dijkstra's algorithm][dijkstra]
75//! to solve the [shortest path problem][sssp] on a [directed graph][dir_graph].
76//! It shows how to use [`BinaryHeap`] with custom types.
77//!
78//! [dijkstra]: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
79//! [sssp]: https://en.wikipedia.org/wiki/Shortest_path_problem
80//! [dir_graph]: https://en.wikipedia.org/wiki/Directed_graph
81//!
82//! ```rust
83//! use mut_binary_heap::BinaryHeap;
84//! use std::cmp::Ordering;
85//!
86//! #[derive(Copy, Clone, Eq, PartialEq)]
87//! struct Node {
88//! cost: usize,
89//! position: usize,
90//! }
91//!
92//! // The priority queue depends on `Ord`.
93//! // Explicitly implement the trait so the queue becomes a min-heap
94//! // instead of a max-heap.
95//! impl Ord for Node {
96//! fn cmp(&self, other: &Self) -> Ordering {
97//! // Notice that the we flip the ordering on costs.
98//! // In case of a tie we compare positions - this step is necessary
99//! // to make implementations of `PartialEq` and `Ord` consistent.
100//! other
101//! .cost
102//! .cmp(&self.cost)
103//! .then_with(|| self.position.cmp(&other.position))
104//! }
105//! }
106//!
107//! // `PartialOrd` needs to be implemented as well.
108//! impl PartialOrd for Node {
109//! fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
110//! Some(self.cmp(other))
111//! }
112//! }
113//!
114//! // Each node is represented as a `usize`, for a shorter implementation.
115//! struct Edge {
116//! node: usize,
117//! cost: usize,
118//! }
119//!
120//! // Dijkstra's shortest path algorithm.
121//!
122//! // Start at `start` and use `dist` to track the current shortest distance
123//! // to each node.
124//! fn shortest_path(edges: &Vec<Vec<Edge>>, start: usize, goal: usize) -> Option<usize> {
125//! let mut heap: BinaryHeap<usize, Node> = BinaryHeap::new();
126//! heap.push(
127//! start,
128//! Node {
129//! cost: 0,
130//! position: start,
131//! },
132//! );
133//!
134//! while let Some(Node { cost, position }) = heap.pop() {
135//! if position == goal {
136//! return Some(cost);
137//! }
138//!
139//! for edge in &edges[position] {
140//! let next_cost = cost + edge.cost;
141//!
142//! // if the edge points to a node that is already in the heap, check
143//! // if it's cost is greater than the cost via this edge.
144//! // Note that normally dijkstra would also have a closed list with all
145//! // nodes that we have already visited. That closed list is also used to
146//! // keep track of the path we have taken.
147//! // To simplify this example we ignore that and only calculate the cost
148//! // to the goal.
149// FIXME why can't i use let Some(node) = heap.pop(). rust complains about the borrow persisting into the else branch
150//! if heap.contains_key(&edge.node) {
151//! let mut node = heap.get_mut(&edge.node).unwrap();
152//! assert_eq!(node.position, edge.node);
153//! if next_cost < node.cost {
154//! node.cost = next_cost;
155//! }
156//! // by dropping `node` the heap is autmatically updated.
157//! } else {
158//! heap.push(
159//! edge.node,
160//! Node {
161//! cost: next_cost,
162//! position: edge.node,
163//! },
164//! );
165//! }
166//! }
167//! }
168//! // If the heap is empty, the goal wasn't found.
169//! None
170//! }
171//!
172//! fn main() {
173//! // This is the directed graph we're going to use.
174//! // The node numbers correspond to the different states,
175//! // and the edge weights symbolize the cost of moving
176//! // from one node to another.
177//! // Note that the edges are one-way.
178//! //
179//! // 7
180//! // +-----------------+
181//! // | |
182//! // v 1 2 | 2
183//! // 0 -----> 1 -----> 3 ---> 4
184//! // | ^ ^ ^
185//! // | | 1 | |
186//! // | | | 3 | 1
187//! // +------> 2 -------+ |
188//! // 10 | |
189//! // +---------------+
190//! //
191//! // The graph is represented as an adjacency list where each index,
192//! // corresponding to a node value, has a list of outgoing edges.
193//! // Chosen for its efficiency.
194//! let graph = vec![
195//! // Node 0
196//! vec![Edge { node: 2, cost: 10 }, Edge { node: 1, cost: 1 }],
197//! // Node 1
198//! vec![Edge { node: 3, cost: 2 }],
199//! // Node 2
200//! vec![
201//! Edge { node: 1, cost: 1 },
202//! Edge { node: 3, cost: 3 },
203//! Edge { node: 4, cost: 1 },
204//! ],
205//! // Node 3
206//! vec![Edge { node: 0, cost: 7 }, Edge { node: 4, cost: 2 }],
207//! // Node 4
208//! vec![],
209//! ];
210//!
211//! assert_eq!(shortest_path(&graph, 0, 1), Some(1));
212//! assert_eq!(shortest_path(&graph, 0, 3), Some(3));
213//! assert_eq!(shortest_path(&graph, 3, 0), Some(7));
214//! assert_eq!(shortest_path(&graph, 0, 4), Some(5));
215//! assert_eq!(shortest_path(&graph, 4, 0), None);
216//! }
217//! ```
218
219mod binary_heap;
220pub use crate::binary_heap::*;
221
222/// An intermediate trait for specialization of `Extend`.
223// #[doc(hidden)]
224// trait SpecExtend<I: IntoIterator> {
225// /// Extends `self` with the contents of the given iterator.
226// fn spec_extend(&mut self, iter: I);
227// }
228
229#[cfg(test)]
230mod from_liballoc {
231 // The following tests copyed from liballoc/tests/binary_heap.rs
232 // I can't fully confirm what the original authors meant by liballoc.
233 // However this is extremely similar to:
234 // https://github.com/rust-lang/rust/blob/master/library/alloc/src/collections/binary_heap/tests.rs
235 // TODO port tests that we are missing and mark commit hash for future reference
236
237 use super::binary_heap::*;
238
239 #[test]
240 fn test_iterator() {
241 let data = vec![5, 9, 3];
242 let iterout = [9, 5, 3];
243 let heap = BinaryHeap::<_, _>::from(data, |k| k.clone());
244 let mut i = 0;
245 for el in &heap {
246 assert_eq!(*el.1, iterout[i]);
247 i += 1;
248 }
249 }
250
251 // #[test]
252 // fn test_iterator_reverse() {
253 // let data = vec![5, 9, 3];
254 // let iterout = vec![3, 5, 9];
255 // let pq = BinaryHeap::<_, _>::from(data, |k| k.clone());
256
257 // let v: Vec<_> = pq.iter().rev().cloned().collect();
258 // assert_eq!(v, iterout);
259 // }
260
261 // #[test]
262 // fn test_move_iter() {
263 // let data = vec![5, 9, 3];
264 // let iterout = vec![9, 5, 3];
265 // let pq = BinaryHeap::<_, _>::from(data, |k| k.clone());
266
267 // let v: Vec<_> = pq.into_iter().collect();
268 // assert_eq!(v, iterout);
269 // }
270
271 #[test]
272 fn test_move_iter_size_hint() {
273 let data = vec![5, 9];
274 let pq = BinaryHeap::<_, _>::from(data, |k| k.clone());
275
276 let mut it = pq.into_iter();
277
278 assert_eq!(it.size_hint(), (2, Some(2)));
279 assert_eq!(it.next(), Some((9, 9)));
280
281 assert_eq!(it.size_hint(), (1, Some(1)));
282 assert_eq!(it.next(), Some((5, 5)));
283
284 assert_eq!(it.size_hint(), (0, Some(0)));
285 assert_eq!(it.next(), None);
286 }
287
288 // #[test]
289 // fn test_move_iter_reverse() {
290 // let data = vec![5, 9, 3];
291 // let iterout = vec![3, 5, 9];
292 // let pq = BinaryHeap::<_, _>::from(data, |k| k.clone());
293
294 // let v: Vec<_> = pq.into_iter().rev().collect();
295 // assert_eq!(v, iterout);
296 // }
297
298 // #[test]
299 // fn test_into_iter_sorted_collect() {
300 // let heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
301 // let it = heap.into_iter_sorted();
302 // let sorted = it.collect::<Vec<_>>();
303 // assert_eq!(sorted, vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 2, 1, 1, 0]);
304 // }
305
306 #[test]
307 fn test_peek_and_pop() {
308 let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1];
309 let mut sorted = data.clone();
310 sorted.sort();
311 let data = data.into_iter().enumerate().map(|(i, v)| (i, v));
312 let mut heap: BinaryHeap<_, _> = data.collect();
313 while !heap.is_empty() {
314 assert_eq!(heap.peek().unwrap(), sorted.last().unwrap());
315 assert_eq!(heap.pop().unwrap(), sorted.pop().unwrap());
316 }
317 }
318
319 #[test]
320 fn test_peek_mut() {
321 let data = [2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]
322 .into_iter()
323 .enumerate()
324 .map(|(i, v)| (i, v));
325 let mut heap: BinaryHeap<_, _> = data.collect();
326 assert_eq!(heap.peek(), Some(&10));
327 {
328 let mut top = heap.peek_mut().unwrap();
329 *top -= 2;
330 }
331 assert_eq!(heap.peek(), Some(&9));
332 }
333
334 #[test]
335 fn test_peek_mut_pop() {
336 let data = [2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]
337 .into_iter()
338 .enumerate()
339 .map(|(i, v)| (i, v));
340 let mut heap: BinaryHeap<_, _> = data.collect();
341 assert_eq!(heap.peek(), Some(&10));
342 {
343 let mut top = heap.peek_mut().unwrap();
344 *top -= 2;
345 assert_eq!(PeekMut::pop(top), 8);
346 }
347 assert_eq!(heap.peek(), Some(&9));
348 }
349
350 #[test]
351 fn test_push() {
352 let mut heap = BinaryHeap::<_, _>::from(vec![2, 4, 9], |k| k.clone());
353 assert_eq!(heap.len(), 3);
354 assert!(*heap.peek().unwrap() == 9);
355 heap.push(11, 11);
356 assert_eq!(heap.len(), 4);
357 assert!(*heap.peek().unwrap() == 11);
358 heap.push(5, 5);
359 assert_eq!(heap.len(), 5);
360 assert!(*heap.peek().unwrap() == 11);
361 heap.push(27, 27);
362 assert_eq!(heap.len(), 6);
363 assert!(*heap.peek().unwrap() == 27);
364 heap.push(3, 3);
365 assert_eq!(heap.len(), 7);
366 assert!(*heap.peek().unwrap() == 27);
367 heap.push(103, 103);
368 assert_eq!(heap.len(), 8);
369 assert!(*heap.peek().unwrap() == 103);
370 }
371
372 #[test]
373 fn test_push_unique() {
374 let data: Vec<Box<i32>> = [2, 4, 9].iter().map(|v| Box::new(*v)).collect();
375 let mut heap = BinaryHeap::<i32, Box<i32>>::from(data, |k| **k);
376 assert_eq!(heap.len(), 3);
377 assert!(**heap.peek().unwrap() == 9);
378 heap.push(11, Box::new(11));
379 assert_eq!(heap.len(), 4);
380 assert!(**heap.peek().unwrap() == 11);
381 heap.push(5, Box::new(5));
382 assert_eq!(heap.len(), 5);
383 assert!(**heap.peek().unwrap() == 11);
384 heap.push(27, Box::new(27));
385 assert_eq!(heap.len(), 6);
386 assert!(**heap.peek().unwrap() == 27);
387 heap.push(3, Box::new(3));
388 assert_eq!(heap.len(), 7);
389 assert!(**heap.peek().unwrap() == 27);
390 heap.push(103, Box::new(103));
391 assert_eq!(heap.len(), 8);
392 assert!(**heap.peek().unwrap() == 103);
393 }
394
395 // fn check_to_vec(mut data: Vec<i32>) {
396 // let heap = BinaryHeap::from(data.clone());
397 // let mut v = heap.clone().into_vec();
398 // v.sort();
399 // data.sort();
400
401 // assert_eq!(v, data);
402 // assert_eq!(heap.into_sorted_vec(), data);
403 // }
404
405 #[test]
406 fn test_empty_pop() {
407 let mut heap = BinaryHeap::<i32, i32>::new();
408 assert!(heap.pop().is_none());
409 }
410
411 #[test]
412 fn test_empty_peek() {
413 let empty = BinaryHeap::<i32, i32>::new();
414 assert!(empty.peek().is_none());
415 }
416
417 #[test]
418 fn test_empty_peek_mut() {
419 let mut empty = BinaryHeap::<i32, i32>::new();
420 assert!(empty.peek_mut().is_none());
421 }
422
423 // #[test]
424 // fn test_from_iter() {
425 // let xs = vec![9, 8, 7, 6, 5, 4, 3, 2, 1];
426
427 // let mut q: BinaryHeap<_> = xs.iter().rev().cloned().collect();
428
429 // for &x in &xs {
430 // assert_eq!(q.pop().unwrap(), x);
431 // }
432 // }
433
434 // #[test]
435 // fn test_drain() {
436 // let mut q: BinaryHeap<_> = [9, 8, 7, 6, 5, 4, 3, 2, 1].iter().cloned().collect();
437
438 // assert_eq!(q.drain().take(5).count(), 5);
439
440 // assert!(q.is_empty());
441 // }
442
443 // #[test]
444 // fn test_extend_ref() {
445 // let mut a = BinaryHeap::new();
446 // a.push(1);
447 // a.push(2);
448
449 // a.extend(&[3, 4, 5]);
450
451 // assert_eq!(a.len(), 5);
452 // assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]);
453
454 // let mut a = BinaryHeap::new();
455 // a.push(1);
456 // a.push(2);
457 // let mut b = BinaryHeap::new();
458 // b.push(3);
459 // b.push(4);
460 // b.push(5);
461
462 // a.extend(&b);
463
464 // assert_eq!(a.len(), 5);
465 // assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]);
466 // }
467
468 // #[test]
469 // fn test_append() {
470 // let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]);
471 // let mut b = BinaryHeap::from(vec![-20, 5, 43]);
472
473 // a.append(&mut b);
474
475 // assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
476 // assert!(b.is_empty());
477 // }
478
479 // #[test]
480 // fn test_append_to_empty() {
481 // let mut a = BinaryHeap::new();
482 // let mut b = BinaryHeap::from(vec![-20, 5, 43]);
483
484 // a.append(&mut b);
485
486 // assert_eq!(a.into_sorted_vec(), [-20, 5, 43]);
487 // assert!(b.is_empty());
488 // }
489
490 // #[test]
491 // fn test_extend_specialization() {
492 // let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]);
493 // let b = BinaryHeap::from(vec![-20, 5, 43]);
494
495 // a.extend(b);
496
497 // assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
498 // }
499
500 // #[test]
501 // fn test_placement() {
502 // let mut a = BinaryHeap::new();
503 // &mut a <- 2;
504 // &mut a <- 4;
505 // &mut a <- 3;
506 // assert_eq!(a.peek(), Some(&4));
507 // assert_eq!(a.len(), 3);
508 // &mut a <- 1;
509 // assert_eq!(a.into_sorted_vec(), vec![1, 2, 3, 4]);
510 // }
511
512 // #[test]
513 // fn test_placement_panic() {
514 // let mut heap = BinaryHeap::from(vec![1, 2, 3]);
515 // fn mkpanic() -> usize {
516 // panic!()
517 // }
518 // let _ = panic::catch_unwind(panic::AssertUnwindSafe(|| {
519 // &mut heap <- mkpanic();
520 // }));
521 // assert_eq!(heap.len(), 3);
522 // }
523
524 #[allow(dead_code)]
525 fn assert_covariance() {
526 fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
527 d
528 }
529 }
530
531 // old binaryheap failed this test
532 //
533 // Integrity means that all elements are present after a comparison panics,
534 // even if the order might not be correct.
535 //
536 // Destructors must be called exactly once per element.
537 // FIXME: re-enable emscripten once it can unwind again
538 #[test]
539 #[cfg(not(target_os = "emscripten"))]
540 fn panic_safe() {
541 use std::cmp;
542 use std::panic::{self, AssertUnwindSafe};
543 use std::sync::atomic::{AtomicUsize, Ordering};
544
545 use rand::{seq::SliceRandom, thread_rng};
546
547 static DROP_COUNTER: AtomicUsize = AtomicUsize::new(0);
548
549 #[derive(Eq, PartialEq, PartialOrd, Clone, Debug)]
550 struct PanicOrd<T>(T, bool);
551
552 impl<T> Drop for PanicOrd<T> {
553 fn drop(&mut self) {
554 // update global drop count
555 DROP_COUNTER.fetch_add(1, Ordering::SeqCst);
556 }
557 }
558
559 impl<T: Ord> Ord for PanicOrd<T> {
560 fn cmp(&self, other: &Self) -> cmp::Ordering {
561 if self.1 || other.1 {
562 panic!("Panicking comparison");
563 }
564 self.0.cmp(&other.0)
565 }
566 }
567 let mut rng = thread_rng();
568 const DATASZ: usize = 32;
569 // Miri is too slow
570 let ntest = if cfg!(miri) { 1 } else { 10 };
571
572 // don't use 0 in the data -- we want to catch the zeroed-out case.
573 let data = (1..=DATASZ).collect::<Vec<_>>();
574
575 // since it's a fuzzy test, run several tries.
576 for _ in 0..ntest {
577 for i in 1..=DATASZ {
578 DROP_COUNTER.store(0, Ordering::SeqCst);
579
580 let mut panic_ords: Vec<_> = data
581 .iter()
582 .filter(|&&x| x != i)
583 .map(|&x| PanicOrd(x, false))
584 .collect();
585 let panic_item = PanicOrd(i, true);
586
587 // heapify the sane items
588 panic_ords.shuffle(&mut rng);
589 let mut heap = BinaryHeap::<_, _>::from(panic_ords, |p| p.0);
590 let inner_data: Vec<PanicOrd<usize>>;
591
592 {
593 // push the panicking item to the heap and catch the panic
594 let thread_result = {
595 let mut heap_ref = AssertUnwindSafe(&mut heap);
596 panic::catch_unwind(move || {
597 heap_ref.push(panic_item.0, panic_item);
598 })
599 };
600 assert!(thread_result.is_err());
601
602 // Assert no elements were dropped
603 let drops = DROP_COUNTER.load(Ordering::SeqCst);
604 assert!(drops == 0, "Must not drop items. drops={}", drops);
605 inner_data = heap.clone().into_values().collect();
606 drop(heap);
607 }
608 let drops = DROP_COUNTER.load(Ordering::SeqCst);
609 assert_eq!(drops, DATASZ);
610
611 let mut data_sorted = inner_data.into_iter().map(|p| p.0).collect::<Vec<_>>();
612 data_sorted.sort();
613 assert_eq!(data_sorted, data);
614 }
615 }
616 }
617}
618
619#[cfg(feature = "serde")]
620#[cfg(test)]
621mod tests_serde {
622 use super::binary_heap::*;
623 use serde_json;
624
625 #[test]
626 fn deserialized_same_small_vec() {
627 let vec = vec![1, 2, 3];
628 let heap = BinaryHeap::<_, _>::from(vec, |k| k.clone());
629 let serialized = serde_json::to_string(&heap).unwrap();
630 let deserialized: BinaryHeap<i32, i32> = serde_json::from_str(&serialized).unwrap();
631
632 let v0: Vec<_> = heap.into_iter().collect();
633 let v1: Vec<_> = deserialized.into_iter().collect();
634 assert_eq!(v0, v1);
635 }
636 #[test]
637 fn deserialized_same() {
638 let vec: Vec<i32> = (0..1000).collect();
639 let heap = BinaryHeap::<_, _>::from(vec, |k| k.clone());
640 let serialized = serde_json::to_string(&heap).unwrap();
641 let deserialized: BinaryHeap<i32, i32> = serde_json::from_str(&serialized).unwrap();
642
643 let v0: Vec<_> = heap.into_iter().collect();
644 let v1: Vec<_> = deserialized.into_iter().collect();
645 assert_eq!(v0, v1);
646 }
647}