1 //! A priority queue implemented with a binary heap.
3 //! Insertion and popping the largest element have `O(log n)` time complexity.
4 //! Checking the largest element is `O(1)`. Converting a vector to a binary heap
5 //! can be done in-place, and has `O(n)` complexity. A binary heap can also be
6 //! converted to a sorted vector in-place, allowing it to be used for an `O(n
7 //! log n)` in-place heapsort.
11 //! This is a larger example that implements [Dijkstra's algorithm][dijkstra]
12 //! to solve the [shortest path problem][sssp] on a [directed graph][dir_graph].
13 //! It shows how to use [`BinaryHeap`] with custom types.
15 //! [dijkstra]: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
16 //! [sssp]: http://en.wikipedia.org/wiki/Shortest_path_problem
17 //! [dir_graph]: http://en.wikipedia.org/wiki/Directed_graph
18 //! [`BinaryHeap`]: struct.BinaryHeap.html
21 //! use std::cmp::Ordering;
22 //! use std::collections::BinaryHeap;
25 //! #[derive(Copy, Clone, Eq, PartialEq)]
31 //! // The priority queue depends on `Ord`.
32 //! // Explicitly implement the trait so the queue becomes a min-heap
33 //! // instead of a max-heap.
34 //! impl Ord for State {
35 //! fn cmp(&self, other: &State) -> Ordering {
36 //! // Notice that the we flip the ordering on costs.
37 //! // In case of a tie we compare positions - this step is necessary
38 //! // to make implementations of `PartialEq` and `Ord` consistent.
39 //! other.cost.cmp(&self.cost)
40 //! .then_with(|| self.position.cmp(&other.position))
44 //! // `PartialOrd` needs to be implemented as well.
45 //! impl PartialOrd for State {
46 //! fn partial_cmp(&self, other: &State) -> Option<Ordering> {
47 //! Some(self.cmp(other))
51 //! // Each node is represented as an `usize`, for a shorter implementation.
57 //! // Dijkstra's shortest path algorithm.
59 //! // Start at `start` and use `dist` to track the current shortest distance
60 //! // to each node. This implementation isn't memory-efficient as it may leave duplicate
61 //! // nodes in the queue. It also uses `usize::MAX` as a sentinel value,
62 //! // for a simpler implementation.
63 //! fn shortest_path(adj_list: &Vec<Vec<Edge>>, start: usize, goal: usize) -> Option<usize> {
64 //! // dist[node] = current shortest distance from `start` to `node`
65 //! let mut dist: Vec<_> = (0..adj_list.len()).map(|_| usize::MAX).collect();
67 //! let mut heap = BinaryHeap::new();
69 //! // We're at `start`, with a zero cost
71 //! heap.push(State { cost: 0, position: start });
73 //! // Examine the frontier with lower cost nodes first (min-heap)
74 //! while let Some(State { cost, position }) = heap.pop() {
75 //! // Alternatively we could have continued to find all shortest paths
76 //! if position == goal { return Some(cost); }
78 //! // Important as we may have already found a better way
79 //! if cost > dist[position] { continue; }
81 //! // For each node we can reach, see if we can find a way with
82 //! // a lower cost going through this node
83 //! for edge in &adj_list[position] {
84 //! let next = State { cost: cost + edge.cost, position: edge.node };
86 //! // If so, add it to the frontier and continue
87 //! if next.cost < dist[next.position] {
89 //! // Relaxation, we have now found a better way
90 //! dist[next.position] = next.cost;
95 //! // Goal not reachable
100 //! // This is the directed graph we're going to use.
101 //! // The node numbers correspond to the different states,
102 //! // and the edge weights symbolize the cost of moving
103 //! // from one node to another.
104 //! // Note that the edges are one-way.
107 //! // +-----------------+
110 //! // 0 -----> 1 -----> 3 ---> 4
114 //! // +------> 2 -------+ |
116 //! // +---------------+
118 //! // The graph is represented as an adjacency list where each index,
119 //! // corresponding to a node value, has a list of outgoing edges.
120 //! // Chosen for its efficiency.
121 //! let graph = vec![
123 //! vec![Edge { node: 2, cost: 10 },
124 //! Edge { node: 1, cost: 1 }],
126 //! vec![Edge { node: 3, cost: 2 }],
128 //! vec![Edge { node: 1, cost: 1 },
129 //! Edge { node: 3, cost: 3 },
130 //! Edge { node: 4, cost: 1 }],
132 //! vec![Edge { node: 0, cost: 7 },
133 //! Edge { node: 4, cost: 2 }],
137 //! assert_eq!(shortest_path(&graph, 0, 1), Some(1));
138 //! assert_eq!(shortest_path(&graph, 0, 3), Some(3));
139 //! assert_eq!(shortest_path(&graph, 3, 0), Some(7));
140 //! assert_eq!(shortest_path(&graph, 0, 4), Some(5));
141 //! assert_eq!(shortest_path(&graph, 4, 0), None);
145 #![allow(missing_docs)]
146 #![stable(feature = "rust1", since = "1.0.0")]
148 use core
::ops
::{Deref, DerefMut}
;
149 use core
::iter
::{FromIterator, FusedIterator}
;
150 use core
::mem
::{swap, size_of, ManuallyDrop}
;
155 use crate::vec
::{self, Vec}
;
157 use super::SpecExtend
;
159 /// A priority queue implemented with a binary heap.
161 /// This will be a max-heap.
163 /// It is a logic error for an item to be modified in such a way that the
164 /// item's ordering relative to any other item, as determined by the `Ord`
165 /// trait, changes while it is in the heap. This is normally only possible
166 /// through `Cell`, `RefCell`, global state, I/O, or unsafe code.
171 /// use std::collections::BinaryHeap;
173 /// // Type inference lets us omit an explicit type signature (which
174 /// // would be `BinaryHeap<i32>` in this example).
175 /// let mut heap = BinaryHeap::new();
177 /// // We can use peek to look at the next item in the heap. In this case,
178 /// // there's no items in there yet so we get None.
179 /// assert_eq!(heap.peek(), None);
181 /// // Let's add some scores...
186 /// // Now peek shows the most important item in the heap.
187 /// assert_eq!(heap.peek(), Some(&5));
189 /// // We can check the length of a heap.
190 /// assert_eq!(heap.len(), 3);
192 /// // We can iterate over the items in the heap, although they are returned in
193 /// // a random order.
195 /// println!("{}", x);
198 /// // If we instead pop these scores, they should come back in order.
199 /// assert_eq!(heap.pop(), Some(5));
200 /// assert_eq!(heap.pop(), Some(2));
201 /// assert_eq!(heap.pop(), Some(1));
202 /// assert_eq!(heap.pop(), None);
204 /// // We can clear the heap of any remaining items.
207 /// // The heap should now be empty.
208 /// assert!(heap.is_empty())
210 #[stable(feature = "rust1", since = "1.0.0")]
211 pub struct BinaryHeap
<T
> {
215 /// Structure wrapping a mutable reference to the greatest item on a
218 /// This `struct` is created by the [`peek_mut`] method on [`BinaryHeap`]. See
219 /// its documentation for more.
221 /// [`peek_mut`]: struct.BinaryHeap.html#method.peek_mut
222 /// [`BinaryHeap`]: struct.BinaryHeap.html
223 #[stable(feature = "binary_heap_peek_mut", since = "1.12.0")]
224 pub struct PeekMut
<'a
, T
: 'a
+ Ord
> {
225 heap
: &'a
mut BinaryHeap
<T
>,
229 #[stable(feature = "collection_debug", since = "1.17.0")]
230 impl<T
: Ord
+ fmt
::Debug
> fmt
::Debug
for PeekMut
<'_
, T
> {
231 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
232 f
.debug_tuple("PeekMut")
233 .field(&self.heap
.data
[0])
238 #[stable(feature = "binary_heap_peek_mut", since = "1.12.0")]
239 impl<T
: Ord
> Drop
for PeekMut
<'_
, T
> {
242 self.heap
.sift_down(0);
247 #[stable(feature = "binary_heap_peek_mut", since = "1.12.0")]
248 impl<T
: Ord
> Deref
for PeekMut
<'_
, T
> {
250 fn deref(&self) -> &T
{
251 debug_assert
!(!self.heap
.is_empty());
252 // SAFE: PeekMut is only instantiated for non-empty heaps
253 unsafe { self.heap.data.get_unchecked(0) }
257 #[stable(feature = "binary_heap_peek_mut", since = "1.12.0")]
258 impl<T
: Ord
> DerefMut
for PeekMut
<'_
, T
> {
259 fn deref_mut(&mut self) -> &mut T
{
260 debug_assert
!(!self.heap
.is_empty());
261 // SAFE: PeekMut is only instantiated for non-empty heaps
262 unsafe { self.heap.data.get_unchecked_mut(0) }
266 impl<'a
, T
: Ord
> PeekMut
<'a
, T
> {
267 /// Removes the peeked value from the heap and returns it.
268 #[stable(feature = "binary_heap_peek_mut_pop", since = "1.18.0")]
269 pub fn pop(mut this
: PeekMut
<'a
, T
>) -> T
{
270 let value
= this
.heap
.pop().unwrap();
276 #[stable(feature = "rust1", since = "1.0.0")]
277 impl<T
: Clone
> Clone
for BinaryHeap
<T
> {
278 fn clone(&self) -> Self {
279 BinaryHeap { data: self.data.clone() }
282 fn clone_from(&mut self, source
: &Self) {
283 self.data
.clone_from(&source
.data
);
287 #[stable(feature = "rust1", since = "1.0.0")]
288 impl<T
: Ord
> Default
for BinaryHeap
<T
> {
289 /// Creates an empty `BinaryHeap<T>`.
291 fn default() -> BinaryHeap
<T
> {
296 #[stable(feature = "binaryheap_debug", since = "1.4.0")]
297 impl<T
: fmt
::Debug
> fmt
::Debug
for BinaryHeap
<T
> {
298 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
299 f
.debug_list().entries(self.iter()).finish()
303 impl<T
: Ord
> BinaryHeap
<T
> {
304 /// Creates an empty `BinaryHeap` as a max-heap.
311 /// use std::collections::BinaryHeap;
312 /// let mut heap = BinaryHeap::new();
315 #[stable(feature = "rust1", since = "1.0.0")]
316 pub fn new() -> BinaryHeap
<T
> {
317 BinaryHeap { data: vec![] }
320 /// Creates an empty `BinaryHeap` with a specific capacity.
321 /// This preallocates enough memory for `capacity` elements,
322 /// so that the `BinaryHeap` does not have to be reallocated
323 /// until it contains at least that many values.
330 /// use std::collections::BinaryHeap;
331 /// let mut heap = BinaryHeap::with_capacity(10);
334 #[stable(feature = "rust1", since = "1.0.0")]
335 pub fn with_capacity(capacity
: usize) -> BinaryHeap
<T
> {
336 BinaryHeap { data: Vec::with_capacity(capacity) }
339 /// Returns a mutable reference to the greatest item in the binary heap, or
340 /// `None` if it is empty.
342 /// Note: If the `PeekMut` value is leaked, the heap may be in an
343 /// inconsistent state.
350 /// use std::collections::BinaryHeap;
351 /// let mut heap = BinaryHeap::new();
352 /// assert!(heap.peek_mut().is_none());
358 /// let mut val = heap.peek_mut().unwrap();
361 /// assert_eq!(heap.peek(), Some(&2));
363 #[stable(feature = "binary_heap_peek_mut", since = "1.12.0")]
364 pub fn peek_mut(&mut self) -> Option
<PeekMut
<'_
, T
>> {
375 /// Removes the greatest item from the binary heap and returns it, or `None` if it
383 /// use std::collections::BinaryHeap;
384 /// let mut heap = BinaryHeap::from(vec![1, 3]);
386 /// assert_eq!(heap.pop(), Some(3));
387 /// assert_eq!(heap.pop(), Some(1));
388 /// assert_eq!(heap.pop(), None);
390 #[stable(feature = "rust1", since = "1.0.0")]
391 pub fn pop(&mut self) -> Option
<T
> {
392 self.data
.pop().map(|mut item
| {
393 if !self.is_empty() {
394 swap(&mut item
, &mut self.data
[0]);
395 self.sift_down_to_bottom(0);
401 /// Pushes an item onto the binary heap.
408 /// use std::collections::BinaryHeap;
409 /// let mut heap = BinaryHeap::new();
414 /// assert_eq!(heap.len(), 3);
415 /// assert_eq!(heap.peek(), Some(&5));
417 #[stable(feature = "rust1", since = "1.0.0")]
418 pub fn push(&mut self, item
: T
) {
419 let old_len
= self.len();
420 self.data
.push(item
);
421 self.sift_up(0, old_len
);
424 /// Consumes the `BinaryHeap` and returns a vector in sorted
425 /// (ascending) order.
432 /// use std::collections::BinaryHeap;
434 /// let mut heap = BinaryHeap::from(vec![1, 2, 4, 5, 7]);
438 /// let vec = heap.into_sorted_vec();
439 /// assert_eq!(vec, [1, 2, 3, 4, 5, 6, 7]);
441 #[stable(feature = "binary_heap_extras_15", since = "1.5.0")]
442 pub fn into_sorted_vec(mut self) -> Vec
<T
> {
443 let mut end
= self.len();
446 self.data
.swap(0, end
);
447 self.sift_down_range(0, end
);
452 // The implementations of sift_up and sift_down use unsafe blocks in
453 // order to move an element out of the vector (leaving behind a
454 // hole), shift along the others and move the removed element back into the
455 // vector at the final location of the hole.
456 // The `Hole` type is used to represent this, and make sure
457 // the hole is filled back at the end of its scope, even on panic.
458 // Using a hole reduces the constant factor compared to using swaps,
459 // which involves twice as many moves.
460 fn sift_up(&mut self, start
: usize, pos
: usize) -> usize {
462 // Take out the value at `pos` and create a hole.
463 let mut hole
= Hole
::new(&mut self.data
, pos
);
465 while hole
.pos() > start
{
466 let parent
= (hole
.pos() - 1) / 2;
467 if hole
.element() <= hole
.get(parent
) {
470 hole
.move_to(parent
);
476 /// Take an element at `pos` and move it down the heap,
477 /// while its children are larger.
478 fn sift_down_range(&mut self, pos
: usize, end
: usize) {
480 let mut hole
= Hole
::new(&mut self.data
, pos
);
481 let mut child
= 2 * pos
+ 1;
483 let right
= child
+ 1;
484 // compare with the greater of the two children
485 if right
< end
&& !(hole
.get(child
) > hole
.get(right
)) {
488 // if we are already in order, stop.
489 if hole
.element() >= hole
.get(child
) {
493 child
= 2 * hole
.pos() + 1;
498 fn sift_down(&mut self, pos
: usize) {
499 let len
= self.len();
500 self.sift_down_range(pos
, len
);
503 /// Take an element at `pos` and move it all the way down the heap,
504 /// then sift it up to its position.
506 /// Note: This is faster when the element is known to be large / should
507 /// be closer to the bottom.
508 fn sift_down_to_bottom(&mut self, mut pos
: usize) {
509 let end
= self.len();
512 let mut hole
= Hole
::new(&mut self.data
, pos
);
513 let mut child
= 2 * pos
+ 1;
515 let right
= child
+ 1;
516 // compare with the greater of the two children
517 if right
< end
&& !(hole
.get(child
) > hole
.get(right
)) {
521 child
= 2 * hole
.pos() + 1;
525 self.sift_up(start
, pos
);
528 fn rebuild(&mut self) {
529 let mut n
= self.len() / 2;
536 /// Moves all the elements of `other` into `self`, leaving `other` empty.
543 /// use std::collections::BinaryHeap;
545 /// let v = vec![-10, 1, 2, 3, 3];
546 /// let mut a = BinaryHeap::from(v);
548 /// let v = vec![-20, 5, 43];
549 /// let mut b = BinaryHeap::from(v);
551 /// a.append(&mut b);
553 /// assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
554 /// assert!(b.is_empty());
556 #[stable(feature = "binary_heap_append", since = "1.11.0")]
557 pub fn append(&mut self, other
: &mut Self) {
558 if self.len() < other
.len() {
562 if other
.is_empty() {
567 fn log2_fast(x
: usize) -> usize {
568 8 * size_of
::<usize>() - (x
.leading_zeros() as usize) - 1
571 // `rebuild` takes O(len1 + len2) operations
572 // and about 2 * (len1 + len2) comparisons in the worst case
573 // while `extend` takes O(len2 * log_2(len1)) operations
574 // and about 1 * len2 * log_2(len1) comparisons in the worst case,
575 // assuming len1 >= len2.
577 fn better_to_rebuild(len1
: usize, len2
: usize) -> bool
{
578 2 * (len1
+ len2
) < len2
* log2_fast(len1
)
581 if better_to_rebuild(self.len(), other
.len()) {
582 self.data
.append(&mut other
.data
);
585 self.extend(other
.drain());
590 impl<T
> BinaryHeap
<T
> {
591 /// Returns an iterator visiting all values in the underlying vector, in
599 /// use std::collections::BinaryHeap;
600 /// let heap = BinaryHeap::from(vec![1, 2, 3, 4]);
602 /// // Print 1, 2, 3, 4 in arbitrary order
603 /// for x in heap.iter() {
604 /// println!("{}", x);
607 #[stable(feature = "rust1", since = "1.0.0")]
608 pub fn iter(&self) -> Iter
<'_
, T
> {
609 Iter { iter: self.data.iter() }
612 /// Returns the greatest item in the binary heap, or `None` if it is empty.
619 /// use std::collections::BinaryHeap;
620 /// let mut heap = BinaryHeap::new();
621 /// assert_eq!(heap.peek(), None);
626 /// assert_eq!(heap.peek(), Some(&5));
629 #[stable(feature = "rust1", since = "1.0.0")]
630 pub fn peek(&self) -> Option
<&T
> {
634 /// Returns the number of elements the binary heap can hold without reallocating.
641 /// use std::collections::BinaryHeap;
642 /// let mut heap = BinaryHeap::with_capacity(100);
643 /// assert!(heap.capacity() >= 100);
646 #[stable(feature = "rust1", since = "1.0.0")]
647 pub fn capacity(&self) -> usize {
651 /// Reserves the minimum capacity for exactly `additional` more elements to be inserted in the
652 /// given `BinaryHeap`. Does nothing if the capacity is already sufficient.
654 /// Note that the allocator may give the collection more space than it requests. Therefore
655 /// capacity can not be relied upon to be precisely minimal. Prefer [`reserve`] if future
656 /// insertions are expected.
660 /// Panics if the new capacity overflows `usize`.
667 /// use std::collections::BinaryHeap;
668 /// let mut heap = BinaryHeap::new();
669 /// heap.reserve_exact(100);
670 /// assert!(heap.capacity() >= 100);
674 /// [`reserve`]: #method.reserve
675 #[stable(feature = "rust1", since = "1.0.0")]
676 pub fn reserve_exact(&mut self, additional
: usize) {
677 self.data
.reserve_exact(additional
);
680 /// Reserves capacity for at least `additional` more elements to be inserted in the
681 /// `BinaryHeap`. The collection may reserve more space to avoid frequent reallocations.
685 /// Panics if the new capacity overflows `usize`.
692 /// use std::collections::BinaryHeap;
693 /// let mut heap = BinaryHeap::new();
694 /// heap.reserve(100);
695 /// assert!(heap.capacity() >= 100);
698 #[stable(feature = "rust1", since = "1.0.0")]
699 pub fn reserve(&mut self, additional
: usize) {
700 self.data
.reserve(additional
);
703 /// Discards as much additional capacity as possible.
710 /// use std::collections::BinaryHeap;
711 /// let mut heap: BinaryHeap<i32> = BinaryHeap::with_capacity(100);
713 /// assert!(heap.capacity() >= 100);
714 /// heap.shrink_to_fit();
715 /// assert!(heap.capacity() == 0);
717 #[stable(feature = "rust1", since = "1.0.0")]
718 pub fn shrink_to_fit(&mut self) {
719 self.data
.shrink_to_fit();
722 /// Discards capacity with a lower bound.
724 /// The capacity will remain at least as large as both the length
725 /// and the supplied value.
727 /// Panics if the current capacity is smaller than the supplied
728 /// minimum capacity.
733 /// #![feature(shrink_to)]
734 /// use std::collections::BinaryHeap;
735 /// let mut heap: BinaryHeap<i32> = BinaryHeap::with_capacity(100);
737 /// assert!(heap.capacity() >= 100);
738 /// heap.shrink_to(10);
739 /// assert!(heap.capacity() >= 10);
742 #[unstable(feature = "shrink_to", reason = "new API", issue="56431")]
743 pub fn shrink_to(&mut self, min_capacity
: usize) {
744 self.data
.shrink_to(min_capacity
)
747 /// Consumes the `BinaryHeap` and returns the underlying vector
748 /// in arbitrary order.
755 /// use std::collections::BinaryHeap;
756 /// let heap = BinaryHeap::from(vec![1, 2, 3, 4, 5, 6, 7]);
757 /// let vec = heap.into_vec();
759 /// // Will print in some order
761 /// println!("{}", x);
764 #[stable(feature = "binary_heap_extras_15", since = "1.5.0")]
765 pub fn into_vec(self) -> Vec
<T
> {
769 /// Returns the length of the binary heap.
776 /// use std::collections::BinaryHeap;
777 /// let heap = BinaryHeap::from(vec![1, 3]);
779 /// assert_eq!(heap.len(), 2);
781 #[stable(feature = "rust1", since = "1.0.0")]
782 pub fn len(&self) -> usize {
786 /// Checks if the binary heap is empty.
793 /// use std::collections::BinaryHeap;
794 /// let mut heap = BinaryHeap::new();
796 /// assert!(heap.is_empty());
802 /// assert!(!heap.is_empty());
804 #[stable(feature = "rust1", since = "1.0.0")]
805 pub fn is_empty(&self) -> bool
{
809 /// Clears the binary heap, returning an iterator over the removed elements.
811 /// The elements are removed in arbitrary order.
818 /// use std::collections::BinaryHeap;
819 /// let mut heap = BinaryHeap::from(vec![1, 3]);
821 /// assert!(!heap.is_empty());
823 /// for x in heap.drain() {
824 /// println!("{}", x);
827 /// assert!(heap.is_empty());
830 #[stable(feature = "drain", since = "1.6.0")]
831 pub fn drain(&mut self) -> Drain
<'_
, T
> {
832 Drain { iter: self.data.drain(..) }
835 /// Drops all items from the binary heap.
842 /// use std::collections::BinaryHeap;
843 /// let mut heap = BinaryHeap::from(vec![1, 3]);
845 /// assert!(!heap.is_empty());
849 /// assert!(heap.is_empty());
851 #[stable(feature = "rust1", since = "1.0.0")]
852 pub fn clear(&mut self) {
857 /// Hole represents a hole in a slice i.e., an index without valid value
858 /// (because it was moved from or duplicated).
859 /// In drop, `Hole` will restore the slice by filling the hole
860 /// position with the value that was originally removed.
861 struct Hole
<'a
, T
: 'a
> {
863 elt
: ManuallyDrop
<T
>,
867 impl<'a
, T
> Hole
<'a
, T
> {
868 /// Create a new `Hole` at index `pos`.
870 /// Unsafe because pos must be within the data slice.
872 unsafe fn new(data
: &'a
mut [T
], pos
: usize) -> Self {
873 debug_assert
!(pos
< data
.len());
874 // SAFE: pos should be inside the slice
875 let elt
= ptr
::read(data
.get_unchecked(pos
));
878 elt
: ManuallyDrop
::new(elt
),
884 fn pos(&self) -> usize {
888 /// Returns a reference to the element removed.
890 fn element(&self) -> &T
{
894 /// Returns a reference to the element at `index`.
896 /// Unsafe because index must be within the data slice and not equal to pos.
898 unsafe fn get(&self, index
: usize) -> &T
{
899 debug_assert
!(index
!= self.pos
);
900 debug_assert
!(index
< self.data
.len());
901 self.data
.get_unchecked(index
)
904 /// Move hole to new location
906 /// Unsafe because index must be within the data slice and not equal to pos.
908 unsafe fn move_to(&mut self, index
: usize) {
909 debug_assert
!(index
!= self.pos
);
910 debug_assert
!(index
< self.data
.len());
911 let index_ptr
: *const _
= self.data
.get_unchecked(index
);
912 let hole_ptr
= self.data
.get_unchecked_mut(self.pos
);
913 ptr
::copy_nonoverlapping(index_ptr
, hole_ptr
, 1);
918 impl<T
> Drop
for Hole
<'_
, T
> {
921 // fill the hole again
924 ptr
::copy_nonoverlapping(&*self.elt
, self.data
.get_unchecked_mut(pos
), 1);
929 /// An iterator over the elements of a `BinaryHeap`.
931 /// This `struct` is created by the [`iter`] method on [`BinaryHeap`]. See its
932 /// documentation for more.
934 /// [`iter`]: struct.BinaryHeap.html#method.iter
935 /// [`BinaryHeap`]: struct.BinaryHeap.html
936 #[stable(feature = "rust1", since = "1.0.0")]
937 pub struct Iter
<'a
, T
: 'a
> {
938 iter
: slice
::Iter
<'a
, T
>,
941 #[stable(feature = "collection_debug", since = "1.17.0")]
942 impl<T
: fmt
::Debug
> fmt
::Debug
for Iter
<'_
, T
> {
943 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
944 f
.debug_tuple("Iter")
945 .field(&self.iter
.as_slice())
950 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
951 #[stable(feature = "rust1", since = "1.0.0")]
952 impl<T
> Clone
for Iter
<'_
, T
> {
953 fn clone(&self) -> Self {
954 Iter { iter: self.iter.clone() }
958 #[stable(feature = "rust1", since = "1.0.0")]
959 impl<'a
, T
> Iterator
for Iter
<'a
, T
> {
963 fn next(&mut self) -> Option
<&'a T
> {
968 fn size_hint(&self) -> (usize, Option
<usize>) {
969 self.iter
.size_hint()
973 #[stable(feature = "rust1", since = "1.0.0")]
974 impl<'a
, T
> DoubleEndedIterator
for Iter
<'a
, T
> {
976 fn next_back(&mut self) -> Option
<&'a T
> {
977 self.iter
.next_back()
981 #[stable(feature = "rust1", since = "1.0.0")]
982 impl<T
> ExactSizeIterator
for Iter
<'_
, T
> {
983 fn is_empty(&self) -> bool
{
988 #[stable(feature = "fused", since = "1.26.0")]
989 impl<T
> FusedIterator
for Iter
<'_
, T
> {}
991 /// An owning iterator over the elements of a `BinaryHeap`.
993 /// This `struct` is created by the [`into_iter`] method on [`BinaryHeap`][`BinaryHeap`]
994 /// (provided by the `IntoIterator` trait). See its documentation for more.
996 /// [`into_iter`]: struct.BinaryHeap.html#method.into_iter
997 /// [`BinaryHeap`]: struct.BinaryHeap.html
998 #[stable(feature = "rust1", since = "1.0.0")]
1000 pub struct IntoIter
<T
> {
1001 iter
: vec
::IntoIter
<T
>,
1004 #[stable(feature = "collection_debug", since = "1.17.0")]
1005 impl<T
: fmt
::Debug
> fmt
::Debug
for IntoIter
<T
> {
1006 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1007 f
.debug_tuple("IntoIter")
1008 .field(&self.iter
.as_slice())
1013 #[stable(feature = "rust1", since = "1.0.0")]
1014 impl<T
> Iterator
for IntoIter
<T
> {
1018 fn next(&mut self) -> Option
<T
> {
1023 fn size_hint(&self) -> (usize, Option
<usize>) {
1024 self.iter
.size_hint()
1028 #[stable(feature = "rust1", since = "1.0.0")]
1029 impl<T
> DoubleEndedIterator
for IntoIter
<T
> {
1031 fn next_back(&mut self) -> Option
<T
> {
1032 self.iter
.next_back()
1036 #[stable(feature = "rust1", since = "1.0.0")]
1037 impl<T
> ExactSizeIterator
for IntoIter
<T
> {
1038 fn is_empty(&self) -> bool
{
1039 self.iter
.is_empty()
1043 #[stable(feature = "fused", since = "1.26.0")]
1044 impl<T
> FusedIterator
for IntoIter
<T
> {}
1046 /// A draining iterator over the elements of a `BinaryHeap`.
1048 /// This `struct` is created by the [`drain`] method on [`BinaryHeap`]. See its
1049 /// documentation for more.
1051 /// [`drain`]: struct.BinaryHeap.html#method.drain
1052 /// [`BinaryHeap`]: struct.BinaryHeap.html
1053 #[stable(feature = "drain", since = "1.6.0")]
1055 pub struct Drain
<'a
, T
: 'a
> {
1056 iter
: vec
::Drain
<'a
, T
>,
1059 #[stable(feature = "drain", since = "1.6.0")]
1060 impl<T
> Iterator
for Drain
<'_
, T
> {
1064 fn next(&mut self) -> Option
<T
> {
1069 fn size_hint(&self) -> (usize, Option
<usize>) {
1070 self.iter
.size_hint()
1074 #[stable(feature = "drain", since = "1.6.0")]
1075 impl<T
> DoubleEndedIterator
for Drain
<'_
, T
> {
1077 fn next_back(&mut self) -> Option
<T
> {
1078 self.iter
.next_back()
1082 #[stable(feature = "drain", since = "1.6.0")]
1083 impl<T
> ExactSizeIterator
for Drain
<'_
, T
> {
1084 fn is_empty(&self) -> bool
{
1085 self.iter
.is_empty()
1089 #[stable(feature = "fused", since = "1.26.0")]
1090 impl<T
> FusedIterator
for Drain
<'_
, T
> {}
1092 #[stable(feature = "binary_heap_extras_15", since = "1.5.0")]
1093 impl<T
: Ord
> From
<Vec
<T
>> for BinaryHeap
<T
> {
1094 fn from(vec
: Vec
<T
>) -> BinaryHeap
<T
> {
1095 let mut heap
= BinaryHeap { data: vec }
;
1101 #[stable(feature = "binary_heap_extras_15", since = "1.5.0")]
1102 impl<T
> From
<BinaryHeap
<T
>> for Vec
<T
> {
1103 fn from(heap
: BinaryHeap
<T
>) -> Vec
<T
> {
1108 #[stable(feature = "rust1", since = "1.0.0")]
1109 impl<T
: Ord
> FromIterator
<T
> for BinaryHeap
<T
> {
1110 fn from_iter
<I
: IntoIterator
<Item
= T
>>(iter
: I
) -> BinaryHeap
<T
> {
1111 BinaryHeap
::from(iter
.into_iter().collect
::<Vec
<_
>>())
1115 #[stable(feature = "rust1", since = "1.0.0")]
1116 impl<T
> IntoIterator
for BinaryHeap
<T
> {
1118 type IntoIter
= IntoIter
<T
>;
1120 /// Creates a consuming iterator, that is, one that moves each value out of
1121 /// the binary heap in arbitrary order. The binary heap cannot be used
1122 /// after calling this.
1129 /// use std::collections::BinaryHeap;
1130 /// let heap = BinaryHeap::from(vec![1, 2, 3, 4]);
1132 /// // Print 1, 2, 3, 4 in arbitrary order
1133 /// for x in heap.into_iter() {
1134 /// // x has type i32, not &i32
1135 /// println!("{}", x);
1138 fn into_iter(self) -> IntoIter
<T
> {
1139 IntoIter { iter: self.data.into_iter() }
1143 #[stable(feature = "rust1", since = "1.0.0")]
1144 impl<'a
, T
> IntoIterator
for &'a BinaryHeap
<T
> {
1146 type IntoIter
= Iter
<'a
, T
>;
1148 fn into_iter(self) -> Iter
<'a
, T
> {
1153 #[stable(feature = "rust1", since = "1.0.0")]
1154 impl<T
: Ord
> Extend
<T
> for BinaryHeap
<T
> {
1156 fn extend
<I
: IntoIterator
<Item
= T
>>(&mut self, iter
: I
) {
1157 <Self as SpecExtend
<I
>>::spec_extend(self, iter
);
1161 impl<T
: Ord
, I
: IntoIterator
<Item
= T
>> SpecExtend
<I
> for BinaryHeap
<T
> {
1162 default fn spec_extend(&mut self, iter
: I
) {
1163 self.extend_desugared(iter
.into_iter());
1167 impl<T
: Ord
> SpecExtend
<BinaryHeap
<T
>> for BinaryHeap
<T
> {
1168 fn spec_extend(&mut self, ref mut other
: BinaryHeap
<T
>) {
1173 impl<T
: Ord
> BinaryHeap
<T
> {
1174 fn extend_desugared
<I
: IntoIterator
<Item
= T
>>(&mut self, iter
: I
) {
1175 let iterator
= iter
.into_iter();
1176 let (lower
, _
) = iterator
.size_hint();
1178 self.reserve(lower
);
1180 for elem
in iterator
{
1186 #[stable(feature = "extend_ref", since = "1.2.0")]
1187 impl<'a
, T
: 'a
+ Ord
+ Copy
> Extend
<&'a T
> for BinaryHeap
<T
> {
1188 fn extend
<I
: IntoIterator
<Item
= &'a T
>>(&mut self, iter
: I
) {
1189 self.extend(iter
.into_iter().cloned());