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