heapless/
binary_heap.rs

1//! A priority queue implemented with a binary heap.
2//!
3//! Insertion and popping the largest element have *O*(log n) time complexity.
4//! Checking the smallest/largest element is *O*(1).
5
6// TODO not yet implemented
7// Converting a vector to a binary heap can be done in-place, and has *O*(n) complexity. A binary
8// heap can also be converted to a sorted vector in-place, allowing it to be used for an
9// *O*(n log n) in-place heapsort.
10
11use core::{
12    cmp::Ordering,
13    fmt,
14    marker::PhantomData,
15    mem::{self, ManuallyDrop},
16    ops::{Deref, DerefMut},
17    ptr, slice,
18};
19
20use crate::vec::{OwnedVecStorage, Vec, VecInner, VecStorage, ViewVecStorage};
21
22/// Min-heap
23pub enum Min {}
24
25/// Max-heap
26pub enum Max {}
27
28/// The binary heap kind: min-heap or max-heap
29pub trait Kind: private::Sealed {
30    #[doc(hidden)]
31    fn ordering() -> Ordering;
32}
33
34impl Kind for Min {
35    fn ordering() -> Ordering {
36        Ordering::Less
37    }
38}
39
40impl Kind for Max {
41    fn ordering() -> Ordering {
42        Ordering::Greater
43    }
44}
45
46/// Sealed traits
47mod private {
48    pub trait Sealed {}
49}
50
51impl private::Sealed for Max {}
52impl private::Sealed for Min {}
53
54/// Base struct for [`BinaryHeap`] and [`BinaryHeapView`], generic over the [`VecStorage`].
55///
56/// In most cases you should use [`BinaryHeap`] or [`BinaryHeapView`] directly. Only use this
57/// struct if you want to write code that's generic over both.
58pub struct BinaryHeapInner<T, K, S: VecStorage<T> + ?Sized> {
59    pub(crate) _kind: PhantomData<K>,
60    pub(crate) data: VecInner<T, usize, S>,
61}
62
63/// A priority queue implemented with a binary heap.
64///
65/// This can be either a min-heap or a max-heap.
66///
67/// It is a logic error for an item to be modified in such a way that the item's ordering relative
68/// to any other item, as determined by the `Ord` trait, changes while it is in the heap. This is
69/// normally only possible through `Cell`, `RefCell`, global state, I/O, or unsafe code.
70///
71/// ```
72/// use heapless::binary_heap::{BinaryHeap, Max};
73///
74/// let mut heap: BinaryHeap<_, Max, 8> = BinaryHeap::new();
75///
76/// // We can use peek to look at the next item in the heap. In this case,
77/// // there's no items in there yet so we get None.
78/// assert_eq!(heap.peek(), None);
79///
80/// // Let's add some scores...
81/// heap.push(1).unwrap();
82/// heap.push(5).unwrap();
83/// heap.push(2).unwrap();
84///
85/// // Now peek shows the most important item in the heap.
86/// assert_eq!(heap.peek(), Some(&5));
87///
88/// // We can check the length of a heap.
89/// assert_eq!(heap.len(), 3);
90///
91/// // We can iterate over the items in the heap, although they are returned in
92/// // a random order.
93/// for x in &heap {
94///     println!("{}", x);
95/// }
96///
97/// // If we instead pop these scores, they should come back in order.
98/// assert_eq!(heap.pop(), Some(5));
99/// assert_eq!(heap.pop(), Some(2));
100/// assert_eq!(heap.pop(), Some(1));
101/// assert_eq!(heap.pop(), None);
102///
103/// // We can clear the heap of any remaining items.
104/// heap.clear();
105///
106/// // The heap should now be empty.
107/// assert!(heap.is_empty())
108/// ```
109pub type BinaryHeap<T, K, const N: usize> = BinaryHeapInner<T, K, OwnedVecStorage<T, N>>;
110
111/// A priority queue implemented with a binary heap.
112///
113/// This can be either a min-heap or a max-heap.
114///
115/// It is a logic error for an item to be modified in such a way that the item's ordering relative
116/// to any other item, as determined by the `Ord` trait, changes while it is in the heap. This is
117/// normally only possible through `Cell`, `RefCell`, global state, I/O, or unsafe code.
118///
119/// ```
120/// use heapless::binary_heap::{BinaryHeap, BinaryHeapView, Max};
121///
122/// let mut heap_buffer: BinaryHeap<_, Max, 8> = BinaryHeap::new();
123/// let heap: &mut BinaryHeapView<_, Max> = &mut heap_buffer;
124///
125/// // We can use peek to look at the next item in the heap. In this case,
126/// // there's no items in there yet so we get None.
127/// assert_eq!(heap.peek(), None);
128///
129/// // Let's add some scores...
130/// heap.push(1).unwrap();
131/// heap.push(5).unwrap();
132/// heap.push(2).unwrap();
133///
134/// // Now peek shows the most important item in the heap.
135/// assert_eq!(heap.peek(), Some(&5));
136///
137/// // We can check the length of a heap.
138/// assert_eq!(heap.len(), 3);
139///
140/// // We can iterate over the items in the heap, although they are returned in
141/// // a random order.
142/// for x in &*heap {
143///     println!("{}", x);
144/// }
145///
146/// // If we instead pop these scores, they should come back in order.
147/// assert_eq!(heap.pop(), Some(5));
148/// assert_eq!(heap.pop(), Some(2));
149/// assert_eq!(heap.pop(), Some(1));
150/// assert_eq!(heap.pop(), None);
151///
152/// // We can clear the heap of any remaining items.
153/// heap.clear();
154///
155/// // The heap should now be empty.
156/// assert!(heap.is_empty())
157/// ```
158pub type BinaryHeapView<T, K> = BinaryHeapInner<T, K, ViewVecStorage<T>>;
159
160impl<T, K, const N: usize> BinaryHeap<T, K, N> {
161    /* Constructors */
162    /// Creates an empty `BinaryHeap` as a $K-heap.
163    ///
164    /// ```
165    /// use heapless::binary_heap::{BinaryHeap, Max};
166    ///
167    /// // allocate the binary heap on the stack
168    /// let mut heap: BinaryHeap<_, Max, 8> = BinaryHeap::new();
169    /// heap.push(4).unwrap();
170    ///
171    /// // allocate the binary heap in a static variable
172    /// static mut HEAP: BinaryHeap<i32, Max, 8> = BinaryHeap::new();
173    /// ```
174    pub const fn new() -> Self {
175        Self {
176            _kind: PhantomData,
177            data: Vec::new(),
178        }
179    }
180}
181
182impl<T, K, const N: usize> BinaryHeap<T, K, N> {
183    /// Returns the underlying `Vec<T,N>`. Order is arbitrary and time is *O*(1).
184    pub fn into_vec(self) -> Vec<T, N, usize> {
185        self.data
186    }
187}
188
189impl<T, K, S: VecStorage<T>> BinaryHeapInner<T, K, S> {
190    /// Get a reference to the `BinaryHeap`, erasing the `N` const-generic.
191    pub fn as_view(&self) -> &BinaryHeapView<T, K> {
192        S::as_binary_heap_view(self)
193    }
194    /// Get a mutable reference to the `BinaryHeap`, erasing the `N` const-generic.
195    pub fn as_mut_view(&mut self) -> &mut BinaryHeapView<T, K> {
196        S::as_binary_heap_view_mut(self)
197    }
198}
199
200impl<T, K, S: VecStorage<T> + ?Sized> BinaryHeapInner<T, K, S>
201where
202    T: Ord,
203    K: Kind,
204{
205    /* Public API */
206    /// Returns the capacity of the binary heap.
207    pub fn capacity(&self) -> usize {
208        self.data.capacity()
209    }
210
211    /// Drops all items from the binary heap.
212    ///
213    /// ```
214    /// use heapless::binary_heap::{BinaryHeap, Max};
215    ///
216    /// let mut heap: BinaryHeap<_, Max, 8> = BinaryHeap::new();
217    /// heap.push(1).unwrap();
218    /// heap.push(3).unwrap();
219    ///
220    /// assert!(!heap.is_empty());
221    ///
222    /// heap.clear();
223    ///
224    /// assert!(heap.is_empty());
225    /// ```
226    pub fn clear(&mut self) {
227        self.data.clear();
228    }
229
230    /// Returns the length of the binary heap.
231    ///
232    /// ```
233    /// use heapless::binary_heap::{BinaryHeap, Max};
234    ///
235    /// let mut heap: BinaryHeap<_, Max, 8> = BinaryHeap::new();
236    /// heap.push(1).unwrap();
237    /// heap.push(3).unwrap();
238    ///
239    /// assert_eq!(heap.len(), 2);
240    /// ```
241    pub fn len(&self) -> usize {
242        self.data.len()
243    }
244
245    /// Checks if the binary heap is empty.
246    ///
247    /// ```
248    /// use heapless::binary_heap::{BinaryHeap, Max};
249    ///
250    /// let mut heap: BinaryHeap<_, Max, 8> = BinaryHeap::new();
251    ///
252    /// assert!(heap.is_empty());
253    ///
254    /// heap.push(3).unwrap();
255    /// heap.push(5).unwrap();
256    /// heap.push(1).unwrap();
257    ///
258    /// assert!(!heap.is_empty());
259    /// ```
260    pub fn is_empty(&self) -> bool {
261        self.len() == 0
262    }
263
264    /// Checks if the binary heap is full.
265    ///
266    /// ```
267    /// use heapless::binary_heap::{BinaryHeap, Max};
268    ///
269    /// let mut heap: BinaryHeap<_, Max, 4> = BinaryHeap::new();
270    ///
271    /// assert!(!heap.is_full());
272    ///
273    /// heap.push(1).unwrap();
274    /// heap.push(2).unwrap();
275    /// heap.push(3).unwrap();
276    /// heap.push(4).unwrap();
277    ///
278    /// assert!(heap.is_full());
279    /// ```
280    pub fn is_full(&self) -> bool {
281        self.len() == self.capacity()
282    }
283
284    /// Returns an iterator visiting all values in the underlying vector, in arbitrary order.
285    ///
286    /// ```
287    /// use heapless::binary_heap::{BinaryHeap, Max};
288    ///
289    /// let mut heap: BinaryHeap<_, Max, 8> = BinaryHeap::new();
290    /// heap.push(1).unwrap();
291    /// heap.push(2).unwrap();
292    /// heap.push(3).unwrap();
293    /// heap.push(4).unwrap();
294    ///
295    /// // Print 1, 2, 3, 4 in arbitrary order
296    /// for x in heap.iter() {
297    ///     println!("{}", x);
298    /// }
299    /// ```
300    pub fn iter(&self) -> slice::Iter<'_, T> {
301        self.data.as_slice().iter()
302    }
303
304    /// Returns a mutable iterator visiting all values in the underlying vector, in arbitrary order.
305    ///
306    /// **WARNING** Mutating the items in the binary heap can leave the heap in an inconsistent
307    /// state.
308    pub fn iter_mut(&mut self) -> slice::IterMut<'_, T> {
309        self.data.as_mut_slice().iter_mut()
310    }
311
312    /// Returns the *top* (greatest if max-heap, smallest if min-heap) item in the binary heap, or
313    /// None if it is empty.
314    ///
315    /// ```
316    /// use heapless::binary_heap::{BinaryHeap, Max};
317    ///
318    /// let mut heap: BinaryHeap<_, Max, 8> = BinaryHeap::new();
319    /// assert_eq!(heap.peek(), None);
320    ///
321    /// heap.push(1).unwrap();
322    /// heap.push(5).unwrap();
323    /// heap.push(2).unwrap();
324    /// assert_eq!(heap.peek(), Some(&5));
325    /// ```
326    pub fn peek(&self) -> Option<&T> {
327        self.data.as_slice().first()
328    }
329
330    /// Returns a mutable reference to the greatest item in the binary heap, or
331    /// `None` if it is empty.
332    ///
333    /// Note: If the `PeekMut` value is leaked, the heap may be in an
334    /// inconsistent state.
335    ///
336    /// # Examples
337    ///
338    /// Basic usage:
339    ///
340    /// ```
341    /// use heapless::binary_heap::{BinaryHeap, Max};
342    ///
343    /// let mut heap: BinaryHeap<_, Max, 8> = BinaryHeap::new();
344    /// assert!(heap.peek_mut().is_none());
345    ///
346    /// heap.push(1);
347    /// heap.push(5);
348    /// heap.push(2);
349    /// {
350    ///     let mut val = heap.peek_mut().unwrap();
351    ///     *val = 0;
352    /// }
353    ///
354    /// assert_eq!(heap.peek(), Some(&2));
355    /// ```
356    pub fn peek_mut(&mut self) -> Option<PeekMutInner<'_, T, K, S>> {
357        if self.is_empty() {
358            None
359        } else {
360            Some(PeekMutInner {
361                heap: self,
362                sift: true,
363            })
364        }
365    }
366
367    /// Removes the *top* (greatest if max-heap, smallest if min-heap) item from the binary heap and
368    /// returns it, or None if it is empty.
369    ///
370    /// ```
371    /// use heapless::binary_heap::{BinaryHeap, Max};
372    ///
373    /// let mut heap: BinaryHeap<_, Max, 8> = BinaryHeap::new();
374    /// heap.push(1).unwrap();
375    /// heap.push(3).unwrap();
376    ///
377    /// assert_eq!(heap.pop(), Some(3));
378    /// assert_eq!(heap.pop(), Some(1));
379    /// assert_eq!(heap.pop(), None);
380    /// ```
381    pub fn pop(&mut self) -> Option<T> {
382        if self.is_empty() {
383            None
384        } else {
385            Some(unsafe { self.pop_unchecked() })
386        }
387    }
388
389    /// Removes the *top* (greatest if max-heap, smallest if min-heap) item from the binary heap and
390    /// returns it, without checking if the binary heap is empty.
391    ///
392    /// # Safety
393    ///
394    /// The binary heap must not be empty.
395    ///
396    /// # Example
397    ///
398    /// ```
399    /// use heapless::binary_heap::{BinaryHeap, Max};
400    ///
401    /// let mut heap: BinaryHeap<_, Max, 8> = BinaryHeap::new();
402    /// heap.push(42)?;
403    ///
404    /// // SAFETY: We just pushed a number onto the heap, so it cannot be empty.
405    /// let val = unsafe { heap.pop_unchecked() };
406    /// assert_eq!(val, 42);
407    /// # Ok::<(), u8>(())
408    /// ```
409    pub unsafe fn pop_unchecked(&mut self) -> T {
410        let mut item = self.data.pop_unchecked();
411
412        if !self.is_empty() {
413            mem::swap(&mut item, self.data.as_mut_slice().get_unchecked_mut(0));
414            self.sift_down_to_bottom(0);
415        }
416        item
417    }
418
419    /// Pushes an item onto the binary heap.
420    ///
421    /// ```
422    /// use heapless::binary_heap::{BinaryHeap, Max};
423    ///
424    /// let mut heap: BinaryHeap<_, Max, 8> = BinaryHeap::new();
425    /// heap.push(3).unwrap();
426    /// heap.push(5).unwrap();
427    /// heap.push(1).unwrap();
428    ///
429    /// assert_eq!(heap.len(), 3);
430    /// assert_eq!(heap.peek(), Some(&5));
431    /// ```
432    pub fn push(&mut self, item: T) -> Result<(), T> {
433        if self.data.is_full() {
434            return Err(item);
435        }
436
437        unsafe { self.push_unchecked(item) }
438        Ok(())
439    }
440
441    /// Pushes an item onto the binary heap without first checking if it's full.
442    ///
443    /// # Safety
444    ///
445    /// The binary heap must not be full.
446    ///
447    /// # Example
448    ///
449    /// ```
450    /// use heapless::binary_heap::{BinaryHeap, Max};
451    ///
452    /// let mut heap: BinaryHeap<_, Max, 8> = BinaryHeap::new();
453    ///
454    /// // SAFETY: We just created an empty heap of size 8, so it cannot be full.
455    /// unsafe { heap.push_unchecked(42) };
456    /// assert_eq!(heap.len(), 1);
457    /// assert_eq!(heap.peek(), Some(&42));
458    /// ```
459    pub unsafe fn push_unchecked(&mut self, item: T) {
460        let old_len = self.len();
461        self.data.push_unchecked(item);
462        self.sift_up(0, old_len);
463    }
464
465    /* Private API */
466    fn sift_down_to_bottom(&mut self, mut pos: usize) {
467        let end = self.len();
468        let start = pos;
469        unsafe {
470            let mut hole = Hole::new(self.data.as_mut_slice(), pos);
471            let mut child = 2 * pos + 1;
472            while child < end {
473                let right = child + 1;
474                // compare with the greater of the two children
475                if right < end && hole.get(child).cmp(hole.get(right)) != K::ordering() {
476                    child = right;
477                }
478                hole.move_to(child);
479                child = 2 * hole.pos() + 1;
480            }
481            pos = hole.pos;
482        }
483        self.sift_up(start, pos);
484    }
485
486    fn sift_up(&mut self, start: usize, pos: usize) -> usize {
487        unsafe {
488            // Take out the value at `pos` and create a hole.
489            let mut hole = Hole::new(self.data.as_mut_slice(), pos);
490
491            while hole.pos() > start {
492                let parent = (hole.pos() - 1) / 2;
493                if hole.element().cmp(hole.get(parent)) != K::ordering() {
494                    break;
495                }
496                hole.move_to(parent);
497            }
498            hole.pos()
499        }
500    }
501}
502
503/// Hole represents a hole in a slice i.e. an index without valid value
504/// (because it was moved from or duplicated).
505/// In drop, `Hole` will restore the slice by filling the hole
506/// position with the value that was originally removed.
507struct Hole<'a, T> {
508    data: &'a mut [T],
509    /// `elt` is always `Some` from new until drop.
510    elt: ManuallyDrop<T>,
511    pos: usize,
512}
513
514impl<'a, T> Hole<'a, T> {
515    /// Create a new Hole at index `pos`.
516    ///
517    /// Unsafe because pos must be within the data slice.
518    #[inline]
519    unsafe fn new(data: &'a mut [T], pos: usize) -> Self {
520        debug_assert!(pos < data.len());
521        let elt = ptr::read(data.get_unchecked(pos));
522        Hole {
523            data,
524            elt: ManuallyDrop::new(elt),
525            pos,
526        }
527    }
528
529    #[inline]
530    fn pos(&self) -> usize {
531        self.pos
532    }
533
534    /// Returns a reference to the element removed.
535    #[inline]
536    fn element(&self) -> &T {
537        &self.elt
538    }
539
540    /// Returns a reference to the element at `index`.
541    ///
542    /// Unsafe because index must be within the data slice and not equal to pos.
543    #[inline]
544    unsafe fn get(&self, index: usize) -> &T {
545        debug_assert!(index != self.pos);
546        debug_assert!(index < self.data.len());
547        self.data.get_unchecked(index)
548    }
549
550    /// Move hole to new location
551    ///
552    /// Unsafe because index must be within the data slice and not equal to pos.
553    #[inline]
554    unsafe fn move_to(&mut self, index: usize) {
555        debug_assert!(index != self.pos);
556        debug_assert!(index < self.data.len());
557        let ptr = self.data.as_mut_ptr();
558        let index_ptr: *const _ = ptr.add(index);
559        let hole_ptr = ptr.add(self.pos);
560        ptr::copy_nonoverlapping(index_ptr, hole_ptr, 1);
561        self.pos = index;
562    }
563}
564
565/// Structure wrapping a mutable reference to the greatest item on a
566/// `BinaryHeap`.
567///
568/// This `struct` is created by [`BinaryHeapInner::peek_mut`].
569/// See its documentation for more.
570pub struct PeekMutInner<'a, T, K, S>
571where
572    T: Ord,
573    K: Kind,
574    S: VecStorage<T> + ?Sized,
575{
576    heap: &'a mut BinaryHeapInner<T, K, S>,
577    sift: bool,
578}
579
580/// Structure wrapping a mutable reference to the greatest item on a
581/// `BinaryHeap`.
582///
583/// This `struct` is created by [`BinaryHeap::peek_mut`].
584/// See its documentation for more.
585pub type PeekMut<'a, T, K, const N: usize> = PeekMutInner<'a, T, K, OwnedVecStorage<T, N>>;
586
587/// Structure wrapping a mutable reference to the greatest item on a
588/// `BinaryHeap`.
589///
590/// This `struct` is created by [`BinaryHeapView::peek_mut`].
591/// See its documentation for more.
592pub type PeekMutView<'a, T, K> = PeekMutInner<'a, T, K, ViewVecStorage<T>>;
593
594impl<T, K, S> Drop for PeekMutInner<'_, T, K, S>
595where
596    T: Ord,
597    K: Kind,
598    S: VecStorage<T> + ?Sized,
599{
600    fn drop(&mut self) {
601        if self.sift {
602            self.heap.sift_down_to_bottom(0);
603        }
604    }
605}
606
607impl<T, K, S> Deref for PeekMutInner<'_, T, K, S>
608where
609    T: Ord,
610    K: Kind,
611    S: VecStorage<T> + ?Sized,
612{
613    type Target = T;
614    fn deref(&self) -> &T {
615        debug_assert!(!self.heap.is_empty());
616        // SAFE: PeekMut is only instantiated for non-empty heaps
617        unsafe { self.heap.data.as_slice().get_unchecked(0) }
618    }
619}
620
621impl<T, K, S> DerefMut for PeekMutInner<'_, T, K, S>
622where
623    T: Ord,
624    K: Kind,
625    S: VecStorage<T> + ?Sized,
626{
627    fn deref_mut(&mut self) -> &mut T {
628        debug_assert!(!self.heap.is_empty());
629        // SAFE: PeekMut is only instantiated for non-empty heaps
630        unsafe { self.heap.data.as_mut_slice().get_unchecked_mut(0) }
631    }
632}
633
634impl<T, K, S> PeekMutInner<'_, T, K, S>
635where
636    T: Ord,
637    K: Kind,
638    S: VecStorage<T> + ?Sized,
639{
640    /// Removes the peeked value from the heap and returns it.
641    pub fn pop(mut this: Self) -> T {
642        let value = this.heap.pop().unwrap();
643        this.sift = false;
644        value
645    }
646}
647
648impl<T> Drop for Hole<'_, T> {
649    #[inline]
650    fn drop(&mut self) {
651        // fill the hole again
652        unsafe {
653            let pos = self.pos;
654            ptr::write(self.data.get_unchecked_mut(pos), ptr::read(&*self.elt));
655        }
656    }
657}
658
659impl<T, K, const N: usize> Default for BinaryHeap<T, K, N>
660where
661    T: Ord,
662    K: Kind,
663{
664    fn default() -> Self {
665        Self::new()
666    }
667}
668
669impl<T, K, const N: usize> Clone for BinaryHeap<T, K, N>
670where
671    K: Kind,
672    T: Ord + Clone,
673{
674    fn clone(&self) -> Self {
675        Self {
676            _kind: self._kind,
677            data: self.data.clone(),
678        }
679    }
680}
681
682impl<T, K, S> fmt::Debug for BinaryHeapInner<T, K, S>
683where
684    K: Kind,
685    T: Ord + fmt::Debug,
686    S: VecStorage<T> + ?Sized,
687{
688    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
689        f.debug_list().entries(self.iter()).finish()
690    }
691}
692
693impl<'a, T, K, S> IntoIterator for &'a BinaryHeapInner<T, K, S>
694where
695    K: Kind,
696    T: Ord,
697    S: VecStorage<T> + ?Sized,
698{
699    type Item = &'a T;
700    type IntoIter = slice::Iter<'a, T>;
701
702    fn into_iter(self) -> Self::IntoIter {
703        self.iter()
704    }
705}
706
707#[cfg(test)]
708mod tests {
709    use static_assertions::assert_not_impl_any;
710
711    use super::{BinaryHeap, BinaryHeapView, Max, Min};
712
713    // Ensure a `BinaryHeap` containing `!Send` values stays `!Send` itself.
714    assert_not_impl_any!(BinaryHeap<*const (), Max, 4>: Send);
715    assert_not_impl_any!(BinaryHeap<*const (), Min, 4>: Send);
716
717    #[test]
718    fn static_new() {
719        static mut _B: BinaryHeap<i32, Min, 16> = BinaryHeap::new();
720    }
721
722    #[test]
723    fn drop() {
724        droppable!();
725
726        {
727            let mut v: BinaryHeap<Droppable, Max, 2> = BinaryHeap::new();
728            v.push(Droppable::new()).ok().unwrap();
729            v.push(Droppable::new()).ok().unwrap();
730            v.pop().unwrap();
731        }
732
733        assert_eq!(Droppable::count(), 0);
734
735        {
736            let mut v: BinaryHeap<Droppable, Max, 2> = BinaryHeap::new();
737            v.push(Droppable::new()).ok().unwrap();
738            v.push(Droppable::new()).ok().unwrap();
739        }
740
741        assert_eq!(Droppable::count(), 0);
742
743        {
744            let mut v: BinaryHeap<Droppable, Min, 2> = BinaryHeap::new();
745            v.push(Droppable::new()).ok().unwrap();
746            v.push(Droppable::new()).ok().unwrap();
747            v.pop().unwrap();
748        }
749
750        assert_eq!(Droppable::count(), 0);
751
752        {
753            let mut v: BinaryHeap<Droppable, Min, 2> = BinaryHeap::new();
754            v.push(Droppable::new()).ok().unwrap();
755            v.push(Droppable::new()).ok().unwrap();
756        }
757
758        assert_eq!(Droppable::count(), 0);
759    }
760
761    #[test]
762    fn into_vec() {
763        droppable!();
764
765        let mut h: BinaryHeap<Droppable, Max, 2> = BinaryHeap::new();
766        h.push(Droppable::new()).ok().unwrap();
767        h.push(Droppable::new()).ok().unwrap();
768        h.pop().unwrap();
769
770        assert_eq!(Droppable::count(), 1);
771
772        let v = h.into_vec();
773
774        assert_eq!(Droppable::count(), 1);
775
776        core::mem::drop(v);
777
778        assert_eq!(Droppable::count(), 0);
779    }
780
781    #[test]
782    fn min() {
783        let mut heap = BinaryHeap::<_, Min, 16>::new();
784        heap.push(1).unwrap();
785        heap.push(2).unwrap();
786        heap.push(3).unwrap();
787        heap.push(17).unwrap();
788        heap.push(19).unwrap();
789        heap.push(36).unwrap();
790        heap.push(7).unwrap();
791        heap.push(25).unwrap();
792        heap.push(100).unwrap();
793
794        assert_eq!(
795            heap.iter().cloned().collect::<Vec<_>>(),
796            [1, 2, 3, 17, 19, 36, 7, 25, 100]
797        );
798
799        assert_eq!(heap.pop(), Some(1));
800
801        assert_eq!(
802            heap.iter().cloned().collect::<Vec<_>>(),
803            [2, 17, 3, 25, 19, 36, 7, 100]
804        );
805
806        assert_eq!(heap.pop(), Some(2));
807        assert_eq!(heap.pop(), Some(3));
808        assert_eq!(heap.pop(), Some(7));
809        assert_eq!(heap.pop(), Some(17));
810        assert_eq!(heap.pop(), Some(19));
811        assert_eq!(heap.pop(), Some(25));
812        assert_eq!(heap.pop(), Some(36));
813        assert_eq!(heap.pop(), Some(100));
814        assert_eq!(heap.pop(), None);
815
816        assert!(heap.peek_mut().is_none());
817
818        heap.push(1).unwrap();
819        heap.push(2).unwrap();
820        heap.push(10).unwrap();
821
822        {
823            let mut val = heap.peek_mut().unwrap();
824            *val = 7;
825        }
826
827        assert_eq!(heap.pop(), Some(2));
828        assert_eq!(heap.pop(), Some(7));
829        assert_eq!(heap.pop(), Some(10));
830        assert_eq!(heap.pop(), None);
831    }
832
833    #[test]
834    fn max() {
835        let mut heap = BinaryHeap::<_, Max, 16>::new();
836        heap.push(1).unwrap();
837        heap.push(2).unwrap();
838        heap.push(3).unwrap();
839        heap.push(17).unwrap();
840        heap.push(19).unwrap();
841        heap.push(36).unwrap();
842        heap.push(7).unwrap();
843        heap.push(25).unwrap();
844        heap.push(100).unwrap();
845
846        assert_eq!(
847            heap.iter().cloned().collect::<Vec<_>>(),
848            [100, 36, 19, 25, 3, 2, 7, 1, 17]
849        );
850
851        assert_eq!(heap.pop(), Some(100));
852
853        assert_eq!(
854            heap.iter().cloned().collect::<Vec<_>>(),
855            [36, 25, 19, 17, 3, 2, 7, 1]
856        );
857
858        assert_eq!(heap.pop(), Some(36));
859        assert_eq!(heap.pop(), Some(25));
860        assert_eq!(heap.pop(), Some(19));
861        assert_eq!(heap.pop(), Some(17));
862        assert_eq!(heap.pop(), Some(7));
863        assert_eq!(heap.pop(), Some(3));
864        assert_eq!(heap.pop(), Some(2));
865        assert_eq!(heap.pop(), Some(1));
866        assert_eq!(heap.pop(), None);
867
868        assert!(heap.peek_mut().is_none());
869
870        heap.push(1).unwrap();
871        heap.push(9).unwrap();
872        heap.push(10).unwrap();
873
874        {
875            let mut val = heap.peek_mut().unwrap();
876            *val = 7;
877        }
878
879        assert_eq!(heap.pop(), Some(9));
880        assert_eq!(heap.pop(), Some(7));
881        assert_eq!(heap.pop(), Some(1));
882        assert_eq!(heap.pop(), None);
883    }
884
885    fn _test_variance<'a: 'b, 'b>(x: BinaryHeap<&'a (), Max, 42>) -> BinaryHeap<&'b (), Max, 42> {
886        x
887    }
888    fn _test_variance_view<'a: 'b, 'b, 'c>(
889        x: &'c BinaryHeapView<&'a (), Max>,
890    ) -> &'c BinaryHeapView<&'b (), Max> {
891        x
892    }
893}