min_max_heap/
lib.rs

1#![doc(html_root_url = "https://docs.rs/min-max-heap/1.3.0")]
2//! A double-ended priority queue.
3//!
4//! A min-max-heap is like a binary heap, but it allows extracting both
5//! the minimum and maximum value efficiently. In particular, finding
6//! either the minimum or maximum element is *O*(1). A removal of either
7//! extremum, or an insertion, is *O*(log *n*).
8//!
9//! ## Usage
10//!
11//! It’s [on crates.io](https://crates.io/crates/min-max-heap), so add
12//! this to your `Cargo.toml`:
13//!
14//! ```toml
15//! [dependencies]
16//! min-max-heap = "1.3.0"
17//! ```
18//!
19//! This crate supports Rust version 1.32.0 and later.
20//!
21//! ## References
22//!
23//! My reference for a min-max heap is
24//! [here](http://cglab.ca/~morin/teaching/5408/refs/minmax.pdf). Much
25//! of this code is also based on `BinaryHeap` from the standard
26//! library.
27
28#![warn(missing_docs)]
29
30#[cfg(feature = "serde")]
31use serde::{Serialize, Deserialize};
32
33use std::iter::FromIterator;
34use std::{fmt, mem, slice, vec};
35use std::ops::{Deref, DerefMut};
36
37mod hole;
38mod index;
39
40use self::hole::*;
41
42/// A double-ended priority queue.
43///
44/// Most operations are *O*(log *n*).
45#[derive(Clone, Debug)]
46#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
47pub struct MinMaxHeap<T>(Vec<T>);
48
49impl<T> Default for MinMaxHeap<T> {
50    fn default() -> Self {
51        MinMaxHeap::new()
52    }
53}
54
55impl<T> MinMaxHeap<T> {
56    /// Creates a new, empty `MinMaxHeap`.
57    ///
58    /// *O*(1).
59    pub fn new() -> Self {
60        MinMaxHeap(Vec::new())
61    }
62
63    /// Creates a new, empty `MinMaxHeap` with space allocated to hold
64    /// `len` elements.
65    ///
66    /// *O*(n).
67    pub fn with_capacity(len: usize) -> Self {
68        MinMaxHeap(Vec::with_capacity(len))
69    }
70
71    /// The number of elements in the heap.
72    ///
73    /// *O*(1).
74    pub fn len(&self) -> usize {
75        self.0.len()
76    }
77
78    /// Is the heap empty?
79    ///
80    /// *O*(1).
81    pub fn is_empty(&self) -> bool {
82        self.0.is_empty()
83    }
84}
85
86impl<T: Ord> MinMaxHeap<T> {
87    /// Adds an element to the heap.
88    ///
89    /// Amortized *O*(log *n*); worst-case *O*(*n*) when the backing vector needs to
90    /// grow.
91    pub fn push(&mut self, element: T) {
92        let pos = self.len();
93        self.0.push(element);
94        self.bubble_up(pos);
95    }
96
97    /// Gets a reference to the minimum element, if any.
98    ///
99    /// *O*(1).
100    pub fn peek_min(&self) -> Option<&T> {
101        if self.is_empty() {
102            None
103        } else {
104            Some(&self.0[0])
105        }
106    }
107
108    /// Returns a mutable reference to the minimum element, if any. Once this reference is dropped,
109    /// the heap is adjusted if necessary.
110    ///
111    /// Note: If the `PeekMinMut` value is leaked, the heap may be in an
112    /// inconsistent state.
113    ///
114    /// *O*(1) for the peek; *O*(log *n*) when the reference is dropped.
115    pub fn peek_min_mut(&mut self) -> Option<PeekMinMut<T>> {
116        if self.is_empty() {
117            None
118        } else {
119            Some(PeekMinMut {
120                heap: self,
121                removed: false,
122            })
123        }
124    }
125
126    /// Gets a reference to the maximum element, if any.
127    ///
128    /// *O*(1).
129    pub fn peek_max(&self) -> Option<&T> {
130        self.find_max().map(|i| &self.0[i])
131    }
132
133    /// Returns a mutable reference to the maximum element, if any. Once this reference is dropped,
134    /// the heap is adjusted if necessary.
135    ///
136    /// Note: If the `PeekMaxMut` value is leaked, the heap may be in an
137    /// inconsistent state.
138    ///
139    /// *O*(1) for the peek; *O*(log *n*) when the reference is dropped.
140    pub fn peek_max_mut(&mut self) -> Option<PeekMaxMut<T>> {
141        self.find_max().map(move |i| PeekMaxMut {
142            heap: self,
143            max_index: i,
144            removed: false,
145        })
146    }
147
148    fn find_max_len(&self, len: usize) -> Option<usize> {
149        match len {
150            0 => None,
151            1 => Some(0),
152            2 => Some(1),
153            _ => if self.0[1] > self.0[2] { Some(1) } else { Some(2) }
154        }
155    }
156
157    fn find_max(&self) -> Option<usize> {
158        self.find_max_len(self.len())
159    }
160
161    /// Removes the minimum element, if any.
162    ///
163    /// *O*(log *n*).
164    pub fn pop_min(&mut self) -> Option<T> {
165        self.0.pop().map(|mut item| {
166            if !self.is_empty() {
167                mem::swap(&mut item, &mut self.0[0]);
168                self.trickle_down_min(0);
169            }
170
171            item
172        })
173    }
174
175    /// Removes the maximum element, if any.
176    ///
177    /// *O*(log *n*).
178    pub fn pop_max(&mut self) -> Option<T> {
179        self.find_max().map(|max| {
180            let mut item = self.0.pop().unwrap();
181
182            if max < self.len() {
183                mem::swap(&mut item, &mut self.0[max]);
184                self.trickle_down_max(max);
185            }
186
187            item
188        })
189    }
190
191    /// Pushes an element, then pops the minimum element.
192    ///
193    /// Unlike a push followed by a pop, this combined operation will
194    /// not allocate.
195    ///
196    /// *O*(log *n*).
197    pub fn push_pop_min(&mut self, mut element: T) -> T {
198        if self.is_empty() { return element; }
199
200        if element < self.0[0] { return element; }
201
202        mem::swap(&mut element, &mut self.0[0]);
203        self.trickle_down_min(0);
204        element
205    }
206
207    /// Pushes an element, then pops the maximum element in an optimized
208    /// fashion.
209    ///
210    /// Unlike a push followed by a pop, this combined operation will
211    /// not allocate.
212    ///
213    /// *O*(log *n*).
214    pub fn push_pop_max(&mut self, mut element: T) -> T {
215        if let Some(i) = self.find_max() {
216            if element > self.0[i] { return element }
217
218            mem::swap(&mut element, &mut self.0[i]);
219
220            if self.0[i] < self.0[0] {
221                self.0.swap(0, i);
222            }
223
224            self.trickle_down_max(i);
225            element
226        } else { element }
227    }
228
229    /// Pops the minimum, then pushes an element in an optimized
230    /// fashion.
231    ///
232    /// *O*(log *n*).
233    pub fn replace_min(&mut self, mut element: T) -> Option<T> {
234        if self.is_empty() {
235            self.push(element);
236            return None;
237        }
238
239        mem::swap(&mut element, &mut self.0[0]);
240        self.trickle_down_min(0);
241        Some(element)
242    }
243
244    /// Pops the maximum, then pushes an element in an optimized
245    /// fashion.
246    ///
247    /// *O*(log *n*).
248    pub fn replace_max(&mut self, mut element: T) -> Option<T> {
249        if let Some(i) = self.find_max() {
250            mem::swap(&mut element, &mut self.0[i]);
251
252            if self.0[i] < self.0[0] {
253                self.0.swap(0, i);
254            }
255
256            self.trickle_down_max(i);
257            Some(element)
258        } else {
259            self.push(element);
260            None
261        }
262    }
263
264    /// Returns an ascending (sorted) vector, reusing the heap’s
265    /// storage.
266    ///
267    /// *O*(*n* log *n*).
268    pub fn into_vec_asc(mut self) -> Vec<T> {
269        let mut end = self.len();
270        while let Some(max) = self.find_max_len(end) {
271            end -= 1;
272            self.0.swap(max, end);
273            self.trickle_down_len(max, end);
274        }
275        self.into_vec()
276    }
277
278    /// Returns an descending (sorted) vector, reusing the heap’s
279    /// storage.
280    ///
281    /// *O*(*n* log *n*).
282    pub fn into_vec_desc(mut self) -> Vec<T> {
283        let mut end = self.len();
284        while end > 1 {
285            end -= 1;
286            self.0.swap(0, end);
287            self.trickle_down_min_len(0, end);
288        }
289        self.into_vec()
290    }
291
292    #[inline]
293    fn trickle_down_min(&mut self, pos: usize) {
294        Hole::new(&mut self.0, pos).trickle_down_min();
295    }
296
297    #[inline]
298    fn trickle_down_max(&mut self, pos: usize) {
299        Hole::new(&mut self.0, pos).trickle_down_max();
300    }
301
302    #[inline]
303    fn trickle_down(&mut self, pos: usize) {
304        Hole::new(&mut self.0, pos).trickle_down();
305    }
306
307    #[inline]
308    fn trickle_down_min_len(&mut self, pos: usize, len: usize) {
309        Hole::new(&mut self.0, pos).trickle_down_min_len(len);
310    }
311
312    #[inline]
313    fn trickle_down_len(&mut self, pos: usize, len: usize) {
314        Hole::new(&mut self.0, pos).trickle_down_len(len);
315    }
316
317    #[inline]
318    fn bubble_up(&mut self, pos: usize) {
319        Hole::new(&mut self.0, pos).bubble_up();
320    }
321
322    fn rebuild(&mut self) {
323        let mut n = self.len() / 2;
324        while n > 0 {
325            n -= 1;
326            self.trickle_down(n);
327        }
328    }
329}
330
331impl<T> MinMaxHeap<T> {
332    /// Drops all items from the heap.
333    ///
334    /// *O*(*n*)
335    pub fn clear(&mut self) {
336        self.0.clear();
337    }
338
339    /// The number of elements the heap can hold without reallocating.
340    ///
341    /// *O*(1)
342    pub fn capacity(&self) -> usize {
343        self.0.capacity()
344    }
345
346    /// Reserves the minimum capacity for exactly `additional` more
347    /// elements to be inserted in the given `MinMaxHeap`.
348    ///
349    /// *O*(*n*)
350    ///
351    /// # Panics
352    ///
353    /// Panics if the new capacity overflows `usize`.
354    pub fn reserve_exact(&mut self, additional: usize) {
355        self.0.reserve_exact(additional)
356    }
357
358    /// Reserves the minimum capacity for at least `additional` more
359    /// elements to be inserted in the given `MinMaxHeap`.
360    ///
361    /// *O*(*n*)
362    ///
363    /// # Panics
364    ///
365    /// Panics if the new capacity overflows `usize`.
366    pub fn reserve(&mut self, additional: usize) {
367        self.0.reserve(additional)
368    }
369
370    /// Discards extra capacity.
371    ///
372    /// *O*(*n*)
373    pub fn shrink_to_fit(&mut self) {
374        self.0.shrink_to_fit()
375    }
376
377    /// Consumes the `MinMaxHeap` and returns its elements in a vector
378    /// in arbitrary order.
379    ///
380    /// *O*(*n*)
381    pub fn into_vec(self) -> Vec<T> {
382        self.0
383    }
384
385    /// Returns a borrowing iterator over the min-max-heap’s elements in
386    /// arbitrary order.
387    ///
388    /// *O*(1) on creation, and *O*(1) for each `next()` operation.
389    pub fn iter(&self) -> Iter<T> {
390        Iter(self.0.iter())
391    }
392
393    /// Returns a draining iterator over the min-max-heap’s elements in
394    /// arbitrary order.
395    ///
396    /// *O*(1) on creation, and *O*(1) for each `next()` operation.
397    pub fn drain(&mut self) -> Drain<T> {
398        Drain(self.0.drain(..))
399    }
400
401    /// Returns a draining iterator over the min-max-heap’s elements in
402    /// ascending (min-first) order.
403    ///
404    /// *O*(1) on creation, and *O*(log *n*) for each `next()` operation.
405    pub fn drain_asc(&mut self) -> DrainAsc<T> {
406        DrainAsc(self)
407    }
408
409    /// Returns a draining iterator over the min-max-heap’s elements in
410    /// descending (max-first) order.
411    ///
412    /// *O*(1) on creation, and *O*(log *n*) for each `next()` operation.
413    pub fn drain_desc(&mut self) -> DrainDesc<T> {
414        DrainDesc(self)
415    }
416}
417
418//
419// Iterators
420//
421
422/// A borrowed iterator over the elements of the min-max-heap in
423/// arbitrary order.
424///
425/// This type is created with
426/// [`MinMaxHeap::iter`](struct.MinMaxHeap.html#method.iter).
427pub struct Iter<'a, T: 'a>(slice::Iter<'a, T>);
428
429impl<'a, T> Iterator for Iter<'a, T> {
430    type Item = &'a T;
431    fn next(&mut self) -> Option<Self::Item> { self.0.next() }
432
433    fn size_hint(&self) -> (usize, Option<usize>) {
434        self.0.size_hint()
435    }
436}
437
438impl<'a, T> ExactSizeIterator for Iter<'a, T> { }
439
440impl<'a, T> IntoIterator for &'a MinMaxHeap<T> {
441    type Item = &'a T;
442    type IntoIter = Iter<'a, T>;
443    fn into_iter(self) -> Self::IntoIter { self.iter() }
444}
445
446/// An owning iterator over the elements of the min-max-heap in
447/// arbitrary order.
448pub struct IntoIter<T>(vec::IntoIter<T>);
449
450impl<T> Iterator for IntoIter<T> {
451    type Item = T;
452    fn next(&mut self) -> Option<Self::Item> { self.0.next() }
453
454    fn size_hint(&self) -> (usize, Option<usize>) {
455        self.0.size_hint()
456    }
457}
458
459impl<T> ExactSizeIterator for IntoIter<T> { }
460
461impl<'a, T> IntoIterator for MinMaxHeap<T> {
462    type Item = T;
463    type IntoIter = IntoIter<T>;
464    fn into_iter(self) -> Self::IntoIter {
465        IntoIter(self.0.into_iter())
466    }
467}
468
469/// A draining iterator over the elements of the min-max-heap in
470/// arbitrary order.
471///
472/// This type is created with
473/// [`MinMaxHeap::drain`](struct.MinMaxHeap.html#method.drain).
474pub struct Drain<'a, T: 'a>(vec::Drain<'a, T>);
475
476impl<'a, T> Iterator for Drain<'a, T> {
477    type Item = T;
478    fn next(&mut self) -> Option<Self::Item> { self.0.next() }
479
480    fn size_hint(&self) -> (usize, Option<usize>) {
481        self.0.size_hint()
482    }
483}
484
485impl<'a, T> ExactSizeIterator for Drain<'a, T> { }
486
487impl<T: Ord> FromIterator<T> for MinMaxHeap<T> {
488    fn from_iter<I>(iter: I) -> Self
489            where I: IntoIterator<Item = T> {
490        let mut result = MinMaxHeap::new();
491        result.extend(iter);
492        result
493    }
494}
495
496/// A draining iterator over the elements of the min-max-heap in
497/// ascending (min-first) order.
498///
499/// Note that each `next()` and `next_back()` operation is
500/// *O*(log *n*) time, so this currently provides no performance
501/// advantage over `pop_min()` and `pop_max()`.
502///
503/// This type is created with
504/// [`MinMaxHeap::drain_asc`](struct.MinMaxHeap.html#method.drain_asc).
505#[derive(Debug)]
506pub struct DrainAsc<'a, T: 'a>(&'a mut MinMaxHeap<T>);
507
508/// A draining iterator over the elements of the min-max-heap in
509/// descending (max-first) order.
510///
511/// Note that each `next()` and `next_back()` operation is
512/// *O*(log *n*) time, so this currently provides no performance
513/// advantage over `pop_max()` and `pop_min()`.
514///
515/// This type is created with
516/// [`MinMaxHeap::drain_desc`](struct.MinMaxHeap.html#method.drain_desc).
517#[derive(Debug)]
518pub struct DrainDesc<'a, T: 'a>(&'a mut MinMaxHeap<T>);
519
520impl<'a, T> Drop for DrainAsc<'a, T> {
521    fn drop(&mut self) {
522        let _ = (self.0).0.drain(..);
523    }
524}
525
526impl<'a, T> Drop for DrainDesc<'a, T> {
527    fn drop(&mut self) {
528        let _ = (self.0).0.drain(..);
529    }
530}
531
532impl<'a, T: Ord> Iterator for DrainAsc<'a, T> {
533    type Item = T;
534
535    fn next(&mut self) -> Option<T> {
536        self.0.pop_min()
537    }
538
539    fn size_hint(&self) -> (usize, Option<usize>) {
540        (self.len(), Some(self.len()))
541    }
542}
543
544impl<'a, T: Ord> Iterator for DrainDesc<'a, T> {
545    type Item = T;
546
547    fn next(&mut self) -> Option<T> {
548        self.0.pop_max()
549    }
550
551    fn size_hint(&self) -> (usize, Option<usize>) {
552        (self.len(), Some(self.len()))
553    }
554}
555
556impl<'a, T: Ord> DoubleEndedIterator for DrainAsc<'a, T> {
557    fn next_back(&mut self) -> Option<T> {
558        self.0.pop_max()
559    }
560}
561
562impl<'a, T: Ord> DoubleEndedIterator for DrainDesc<'a, T> {
563    fn next_back(&mut self) -> Option<T> {
564        self.0.pop_min()
565    }
566}
567
568impl<'a, T: Ord> ExactSizeIterator for DrainAsc<'a, T> {
569    fn len(&self) -> usize {
570        self.0.len()
571    }
572}
573
574impl<'a, T: Ord> ExactSizeIterator for DrainDesc<'a, T> {
575    fn len(&self) -> usize {
576        self.0.len()
577    }
578}
579
580//
581// From<Vec<_>>
582//
583
584impl<T: Ord> From<Vec<T>> for MinMaxHeap<T> {
585    fn from(vec: Vec<T>) -> Self {
586        let mut heap = MinMaxHeap(vec);
587        heap.rebuild();
588        heap
589    }
590}
591
592//
593// Extend
594//
595
596impl<T: Ord> Extend<T> for MinMaxHeap<T> {
597    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
598        for elem in iter {
599            self.push(elem)
600        }
601    }
602}
603
604impl<'a, T: Ord + Clone + 'a> Extend<&'a T> for MinMaxHeap<T> {
605    fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
606        for elem in iter {
607            self.push(elem.clone())
608        }
609    }
610}
611
612/// Structure wrapping a mutable reference to the minimum item on a
613/// `MinMaxHeap`.
614///
615/// This `struct` is created by the [`peek_min_mut`] method on [`MinMaxHeap`]. See
616/// its documentation for more.
617///
618/// [`peek_min_mut`]: struct.MinMaxHeap.html#method.peek_min_mut
619/// [`MinMaxHeap`]: struct.MinMaxHeap.html
620pub struct PeekMinMut<'a, T: 'a + Ord> {
621    heap: &'a mut MinMaxHeap<T>,
622    removed: bool,
623}
624
625impl<T: Ord + fmt::Debug> fmt::Debug for PeekMinMut<'_, T> {
626    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
627        f.debug_tuple("PeekMinMut")
628         .field(&self.heap.0[0])
629         .finish()
630    }
631}
632
633impl<'a, T: Ord> Drop for PeekMinMut<'a, T> {
634    fn drop(&mut self) {
635        if !self.removed {
636            self.heap.trickle_down_min(0);
637        }
638    }
639}
640
641impl<'a, T: Ord> Deref for PeekMinMut<'a, T> {
642    type Target = T;
643    fn deref(&self) -> &T {
644        debug_assert!(!self.heap.is_empty());
645        // SAFE: PeekMinMut is only instantiated for non-empty heaps
646        unsafe { self.heap.0.get_unchecked(0) }
647    }
648}
649
650impl<'a, T: Ord> DerefMut for PeekMinMut<'a, T> {
651    fn deref_mut(&mut self) -> &mut T {
652        debug_assert!(!self.heap.is_empty());
653        // SAFE: PeekMinMut is only instantiated for non-empty heaps
654        unsafe { self.heap.0.get_unchecked_mut(0) }
655    }
656}
657
658impl<'a, T: Ord> PeekMinMut<'a, T> {
659    /// Removes the peeked value from the heap and returns it.
660    pub fn pop(mut self) -> T {
661        let value = self.heap.pop_min().unwrap();
662        self.removed = true;
663        value
664    }
665}
666
667/// Structure wrapping a mutable reference to the maximum item on a
668/// `MinMaxHeap`.
669///
670/// This `struct` is created by the [`peek_max_mut`] method on [`MinMaxHeap`]. See
671/// its documentation for more.
672///
673/// [`peek_max_mut`]: struct.MinMaxHeap.html#method.peek_max_mut
674/// [`MinMaxHeap`]: struct.MinMaxHeap.html
675pub struct PeekMaxMut<'a, T: 'a + Ord> {
676    heap: &'a mut MinMaxHeap<T>,
677    max_index: usize,
678    removed: bool,
679}
680
681impl<T: Ord + fmt::Debug> fmt::Debug for PeekMaxMut<'_, T> {
682    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
683        f.debug_tuple("PeekMaxMut")
684         .field(&self.heap.0[self.max_index])
685         .finish()
686    }
687}
688
689impl<'a, T: Ord> Drop for PeekMaxMut<'a, T> {
690    fn drop(&mut self) {
691        if !self.removed {
692            let mut hole = Hole::new(&mut self.heap.0, self.max_index);
693
694            if hole.element() < hole.get_parent() {
695                hole.swap_with_parent();
696            }
697
698            hole.trickle_down_max();
699        }
700    }
701}
702
703impl<'a, T: Ord> Deref for PeekMaxMut<'a, T> {
704    type Target = T;
705    fn deref(&self) -> &T {
706        debug_assert!(self.max_index < self.heap.len());
707        // SAFE: PeekMaxMut is only instantiated for non-empty heaps
708        unsafe { self.heap.0.get_unchecked(self.max_index) }
709    }
710}
711
712impl<'a, T: Ord> DerefMut for PeekMaxMut<'a, T> {
713    fn deref_mut(&mut self) -> &mut T {
714        debug_assert!(self.max_index < self.heap.len());
715        // SAFE: PeekMaxMut is only instantiated for non-empty heaps
716        unsafe { self.heap.0.get_unchecked_mut(self.max_index) }
717    }
718}
719
720impl<'a, T: Ord> PeekMaxMut<'a, T> {
721    /// Removes the peeked value from the heap and returns it.
722    pub fn pop(mut self) -> T {
723        let value = self.heap.pop_max().unwrap();
724        self.removed = true;
725        value
726    }
727}
728
729#[cfg(test)]
730mod tests {
731    extern crate rand;
732
733    use super::*;
734    use self::rand::seq::SliceRandom;
735
736    #[test]
737    fn example() {
738        let mut h = MinMaxHeap::new();
739        assert!(h.is_empty());
740
741        h.push(5);
742        assert!(!h.is_empty());
743        assert_eq!(Some(&5), h.peek_min());
744        assert_eq!(Some(&5), h.peek_max());
745
746        h.push(7);
747        assert_eq!(Some(&5), h.peek_min());
748        assert_eq!(Some(&7), h.peek_max());
749
750        h.push(6);
751        assert_eq!(Some(&5), h.peek_min());
752        assert_eq!(Some(&7), h.peek_max());
753
754        assert_eq!(Some(5), h.pop_min());
755        assert_eq!(Some(7), h.pop_max());
756        assert_eq!(Some(6), h.pop_max());
757        assert_eq!(None, h.pop_min());
758    }
759
760    #[test]
761    fn drain_asc() {
762        let mut h = MinMaxHeap::from(vec![3, 2, 4, 1]);
763        let mut i = h.drain_asc();
764        assert_eq!( i.next(), Some(1) );
765        assert_eq!( i.next(), Some(2) );
766        assert_eq!( i.next(), Some(3) );
767        assert_eq!( i.next(), Some(4) );
768        assert_eq!( i.next(), None );
769    }
770
771    // This test catches a lot:
772    #[test]
773    fn random_vectors() {
774        for i in 0 .. 300 {
775            check_heap(&random_heap(i));
776        }
777    }
778
779    #[test]
780    fn from_vector() {
781        for i in 0 .. 300 {
782            check_heap(&MinMaxHeap::from(random_vec(i)))
783        }
784    }
785
786    fn check_heap(heap: &MinMaxHeap<usize>) {
787        let asc  = iota_asc(heap.len());
788        let desc = iota_desc(heap.len());
789
790        assert_eq!(asc, into_vec_asc(heap.clone()));
791        assert_eq!(desc, into_vec_desc(heap.clone()));
792        assert_eq!(asc, heap.clone().into_vec_asc());
793        assert_eq!(desc, heap.clone().into_vec_desc());
794    }
795
796    fn random_vec(len: usize) -> Vec<usize> {
797        let mut result = (0 .. len).collect::<Vec<_>>();
798        result.shuffle(&mut rand::thread_rng());
799        result
800    }
801
802    fn random_heap(len: usize) -> MinMaxHeap<usize> {
803        MinMaxHeap::from_iter(random_vec(len))
804    }
805
806    fn into_vec_asc(mut heap: MinMaxHeap<usize>) -> Vec<usize> {
807        let mut result = Vec::with_capacity(heap.len());
808        while let Some(elem) = heap.pop_min() {
809            result.push(elem)
810        }
811        result
812    }
813
814    fn into_vec_desc(mut heap: MinMaxHeap<usize>) -> Vec<usize> {
815        let mut result = Vec::with_capacity(heap.len());
816        while let Some(elem) = heap.pop_max() {
817            result.push(elem)
818        }
819        result
820    }
821
822    fn iota_asc(len: usize) -> Vec<usize> {
823        (0 .. len).collect()
824    }
825
826    fn iota_desc(len: usize) -> Vec<usize> {
827        let mut result = (0 .. len).collect::<Vec<_>>();
828        result.reverse();
829        result
830    }
831
832    #[test]
833    fn replace_max() {
834        let mut h = MinMaxHeap::from(vec![1, 2]);
835        assert_eq!(Some(2), h.replace_max(3));
836        assert_eq!(Some(&1), h.peek_min());
837        assert_eq!(Some(&3), h.peek_max());
838
839        assert_eq!(Some(3), h.replace_max(0));
840        assert_eq!(Some(&0), h.peek_min());
841        assert_eq!(Some(&1), h.peek_max());
842    }
843
844    #[test]
845    fn peek_min_mut() {
846        let mut h = MinMaxHeap::from(vec![2, 3, 4]);
847        *h.peek_min_mut().unwrap() = 1;
848        assert_eq!(Some(&1), h.peek_min());
849        assert_eq!(Some(&4), h.peek_max());
850
851        *h.peek_min_mut().unwrap() = 8;
852        assert_eq!(Some(&3), h.peek_min());
853        assert_eq!(Some(&8), h.peek_max());
854
855        assert_eq!(3, h.peek_min_mut().unwrap().pop());
856        assert_eq!(Some(&4), h.peek_min());
857        assert_eq!(Some(&8), h.peek_max());
858    }
859
860    #[test]
861    fn peek_max_mut() {
862        let mut h = MinMaxHeap::from(vec![1, 2]);
863        *h.peek_max_mut().unwrap() = 3;
864        assert_eq!(Some(&1), h.peek_min());
865        assert_eq!(Some(&3), h.peek_max());
866
867        *h.peek_max_mut().unwrap() = 0;
868        assert_eq!(Some(&0), h.peek_min());
869        assert_eq!(Some(&1), h.peek_max());
870
871        assert_eq!(1, h.peek_max_mut().unwrap().pop());
872        assert_eq!(Some(&0), h.peek_min());
873        assert_eq!(Some(&0), h.peek_max());
874    }
875
876    #[test]
877    fn push_pop_max() {
878        let mut h = MinMaxHeap::from(vec![1, 2]);
879        assert_eq!(3, h.push_pop_max(3));
880        assert_eq!(2, h.push_pop_max(0));
881        assert_eq!(Some(&0), h.peek_min());
882        assert_eq!(Some(&1), h.peek_max());
883    }
884}
min_max_heap/lib.rs

min_max_heap/
lib.rs
