Lines Matching refs:heap
2480 let mut heap: BinaryHeap<_> = iter.by_ref().take(1000).collect();
2483 let mut max = heap.peek_mut().unwrap();
2491 heap
8880 mod heap;
9279 // Test on-heap from_fn.
9303 // Test on-heap from_elem.
9535 // Test on-heap push().
13293 let heap = BinaryHeap::from(data);
13295 for el in &heap {
13350 let heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
13351 let it = heap.into_iter_sorted();
13358 let mut heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
13359 let it = heap.drain_sorted();
13380 let heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
13381 check_exact_size_iterator(heap.len(), heap.iter());
13382 check_exact_size_iterator(heap.len(), heap.clone().into_iter());
13383 check_exact_size_iterator(heap.len(), heap.clone().into_iter_sorted());
13384 check_exact_size_iterator(heap.len(), heap.clone().drain());
13385 check_exact_size_iterator(heap.len(), heap.clone().drain_sorted());
13402 let heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
13403 check_trusted_len(heap.len(), heap.clone().into_iter_sorted());
13404 check_trusted_len(heap.len(), heap.clone().drain_sorted());
13412 let mut heap = BinaryHeap::from(data);
13413 while !heap.is_empty() {
13414 assert_eq!(heap.peek().unwrap(), sorted.last().unwrap());
13415 assert_eq!(heap.pop().unwrap(), sorted.pop().unwrap());
13422 let mut heap = BinaryHeap::from(data);
13423 assert_eq!(heap.peek(), Some(&10));
13425 let mut top = heap.peek_mut().unwrap();
13428 assert_eq!(heap.peek(), Some(&9));
13434 let mut heap = BinaryHeap::from(data);
13435 assert_eq!(heap.peek(), Some(&10));
13437 let mut top = heap.peek_mut().unwrap();
13441 assert_eq!(heap.peek(), Some(&9));
13446 let mut heap = BinaryHeap::from(vec![2, 4, 9]);
13447 assert_eq!(heap.len(), 3);
13448 assert!(*heap.peek().unwrap() == 9);
13449 heap.push(11);
13450 assert_eq!(heap.len(), 4);
13451 assert!(*heap.peek().unwrap() == 11);
13452 heap.push(5);
13453 assert_eq!(heap.len(), 5);
13454 assert!(*heap.peek().unwrap() == 11);
13455 heap.push(27);
13456 assert_eq!(heap.len(), 6);
13457 assert!(*heap.peek().unwrap() == 27);
13458 heap.push(3);
13459 assert_eq!(heap.len(), 7);
13460 assert!(*heap.peek().unwrap() == 27);
13461 heap.push(103);
13462 assert_eq!(heap.len(), 8);
13463 assert!(*heap.peek().unwrap() == 103);
13468 let mut heap = BinaryHeap::<Box<_>>::from(vec![box 2, box 4, box 9]);
13469 assert_eq!(heap.len(), 3);
13470 assert!(**heap.peek().unwrap() == 9);
13471 heap.push(box 11);
13472 assert_eq!(heap.len(), 4);
13473 assert!(**heap.peek().unwrap() == 11);
13474 heap.push(box 5);
13475 assert_eq!(heap.len(), 5);
13476 assert!(**heap.peek().unwrap() == 11);
13477 heap.push(box 27);
13478 assert_eq!(heap.len(), 6);
13479 assert!(**heap.peek().unwrap() == 27);
13480 heap.push(box 3);
13481 assert_eq!(heap.len(), 7);
13482 assert!(**heap.peek().unwrap() == 27);
13483 heap.push(box 103);
13484 assert_eq!(heap.len(), 8);
13485 assert!(**heap.peek().unwrap() == 103);
13489 let heap = BinaryHeap::from(data.clone());
13490 let mut v = heap.clone().into_vec();
13495 assert_eq!(heap.into_sorted_vec(), data);
13519 let heap: BinaryHeap<_> = src.into_iter().map(std::convert::identity).collect();
13520 let heap_ptr = heap.iter().next().unwrap() as *const usize;
13522 let sink: Vec<_> = heap.into_iter().map(std::convert::identity).collect();
13529 let mut heap = BinaryHeap::<i32>::new();
13530 assert!(heap.pop().is_none());
13744 let mut heap = BinaryHeap::from(panic_ords);
13748 // push the panicking item to the heap and catch the panic
13750 let mut heap_ref = AssertUnwindSafe(&mut heap);
13760 inner_data = heap.clone().into_vec();
13761 drop(heap);
14449 /// a buffer of memory on the heap without having to worry about all the corner cases
14485 /// Creates the biggest possible `RawVec` (on the system heap)
14494 /// Creates a `RawVec` (on the system heap) with exactly the
14522 /// The `ptr` must be allocated (on the system heap), and with the given `capacity`.
14534 // - 8 if the element size is 1, because any heap allocators is likely
16355 /// This buffer is always stored on the heap.
18522 /// The result is allocated on the heap.
18590 /// No heap allocation is performed, and the string
18608 /// No heap allocation is performed, and the string
18628 /// No heap allocation is performed, and the string
19303 //! heap-allocated values.
19314 //! heap.
19500 //! allocated in the heap. Invoking [`clone`][clone] on [`Rc`] produces a new
19501 //! pointer to the same allocation in the heap. When the last [`Rc`] pointer to a
21447 // to allocate space on the heap. That's not a value a real pointer
23215 /// No heap allocations or atomic operations are used for this conversion.
23227 /// No heap allocations or atomic operations are used for this conversion.
23334 /// allocated in the heap. Invoking [`clone`][clone] on `Arc` produces
23335 /// a new `Arc` instance, which points to the same allocation on the heap as the
23546 // to allocate space on the heap. That's not a value a real pointer
26279 //! does not require any heap allocations to create, and it only
29831 /// is stored in its own individually heap-allocated node. This means that every single insertion
29832 /// triggers a heap-allocation, and every single comparison should be a cache-miss. Since these
44268 //! A priority queue implemented with a binary heap.
44271 //! Checking the largest element is *O*(1). Converting a vector to a binary heap
44272 //! can be done in-place, and has *O*(*n*) complexity. A binary heap can also be
44297 //! // Explicitly implement the trait so the queue becomes a min-heap
44298 //! // instead of a max-heap.
44332 //! let mut heap = BinaryHeap::new();
44336 //! heap.push(State { cost: 0, position: start });
44338 //! // Examine the frontier with lower cost nodes first (min-heap)
44339 //! while let Some(State { cost, position }) = heap.pop() {
44353 //! heap.push(next);
44424 /// A priority queue implemented with a binary heap.
44426 /// This will be a max-heap.
44430 /// trait, changes while it is in the heap. This is normally only possible
44443 /// let mut heap = BinaryHeap::new();
44445 /// // We can use peek to look at the next item in the heap. In this case,
44447 /// assert_eq!(heap.peek(), None);
44450 /// heap.push(1);
44451 /// heap.push(5);
44452 /// heap.push(2);
44454 /// // Now peek shows the most important item in the heap.
44455 /// assert_eq!(heap.peek(), Some(&5));
44457 /// // We can check the length of a heap.
44458 /// assert_eq!(heap.len(), 3);
44460 /// // We can iterate over the items in the heap, although they are returned in
44462 /// for x in &heap {
44467 /// assert_eq!(heap.pop(), Some(5));
44468 /// assert_eq!(heap.pop(), Some(2));
44469 /// assert_eq!(heap.pop(), Some(1));
44470 /// assert_eq!(heap.pop(), None);
44472 /// // We can clear the heap of any remaining items.
44473 /// heap.clear();
44475 /// // The heap should now be empty.
44476 /// assert!(heap.is_empty())
44479 /// ## Min-heap
44482 /// make `BinaryHeap` a min-heap. This makes `heap.pop()` return the smallest
44489 /// let mut heap = BinaryHeap::new();
44492 /// heap.push(Reverse(1));
44493 /// heap.push(Reverse(5));
44494 /// heap.push(Reverse(2));
44497 /// assert_eq!(heap.pop(), Some(Reverse(1)));
44498 /// assert_eq!(heap.pop(), Some(Reverse(2)));
44499 /// assert_eq!(heap.pop(), Some(Reverse(5)));
44500 /// assert_eq!(heap.pop(), None);
44531 heap: &'a mut BinaryHeap<T>,
44538 f.debug_tuple("PeekMut").field(&self.heap.data[0]).finish()
44547 unsafe { self.heap.sift_down(0) };
44556 debug_assert!(!self.heap.is_empty());
44558 unsafe { self.heap.data.get_unchecked(0) }
44565 debug_assert!(!self.heap.is_empty());
44568 unsafe { self.heap.data.get_unchecked_mut(0) }
44573 /// Removes the peeked value from the heap and returns it.
44576 let value = this.heap.pop().unwrap();
44610 /// Creates an empty `BinaryHeap` as a max-heap.
44618 /// let mut heap = BinaryHeap::new();
44619 /// heap.push(4);
44637 /// let mut heap = BinaryHeap::with_capacity(10);
44638 /// heap.push(4);
44645 /// Returns a mutable reference to the greatest item in the binary heap, or
44648 /// Note: If the `PeekMut` value is leaked, the heap may be in an
44657 /// let mut heap = BinaryHeap::new();
44658 /// assert!(heap.peek_mut().is_none());
44660 /// heap.push(1);
44661 /// heap.push(5);
44662 /// heap.push(2);
44664 /// let mut val = heap.peek_mut().unwrap();
44667 /// assert_eq!(heap.peek(), Some(&2));
44676 if self.is_empty() { None } else { Some(PeekMut { heap: self, sift: false }) }
44679 /// Removes the greatest item from the binary heap and returns it, or `None` if it
44688 /// let mut heap = BinaryHeap::from(vec![1, 3]);
44690 /// assert_eq!(heap.pop(), Some(3));
44691 /// assert_eq!(heap.pop(), Some(1));
44692 /// assert_eq!(heap.pop(), None);
44697 /// The worst case cost of `pop` on a heap containing *n* elements is *O*(log(*n*)).
44710 /// Pushes an item onto the binary heap.
44718 /// let mut heap = BinaryHeap::new();
44719 /// heap.push(3);
44720 /// heap.push(5);
44721 /// heap.push(1);
44723 /// assert_eq!(heap.len(), 3);
44724 /// assert_eq!(heap.peek(), Some(&5));
44736 /// sorted order and the amortized cost per push is *O*(log(*n*)) against a heap
44761 /// let mut heap = BinaryHeap::from(vec![1, 2, 4, 5, 7]);
44762 /// heap.push(6);
44763 /// heap.push(3);
44765 /// let vec = heap.into_sorted_vec();
44824 /// Take an element at `pos` and move it down the heap,
44877 /// Take an element at `pos` and move it all the way down the heap,
44922 /// Rebuild assuming data[0..start] is still a proper heap.
45003 /// Returns an iterator which retrieves elements in heap order.
45004 /// The retrieved elements are removed from the original heap.
45005 /// The remaining elements will be removed on drop in heap order.
45019 /// let mut heap = BinaryHeap::from(vec![1, 2, 3, 4, 5]);
45020 /// assert_eq!(heap.len(), 5);
45022 /// drop(heap.drain_sorted()); // removes all elements in heap order
45023 /// assert_eq!(heap.len(), 0);
45044 /// let mut heap = BinaryHeap::from(vec![-10, -5, 1, 2, 4, 13]);
45046 /// heap.retain(|x| x % 2 == 0); // only keep even numbers
45048 /// assert_eq!(heap.into_sorted_vec(), [-10, 2, 4])
45080 /// let heap = BinaryHeap::from(vec![1, 2, 3, 4]);
45083 /// for x in heap.iter() {
45092 /// Returns an iterator which retrieves elements in heap order.
45093 /// This method consumes the original heap.
45102 /// let heap = BinaryHeap::from(vec![1, 2, 3, 4, 5]);
45104 /// assert_eq!(heap.into_iter_sorted().take(2).collect::<Vec<_>>(), vec![5, 4]);
45111 /// Returns the greatest item in the binary heap, or `None` if it is empty.
45119 /// let mut heap = BinaryHeap::new();
45120 /// assert_eq!(heap.peek(), None);
45122 /// heap.push(1);
45123 /// heap.push(5);
45124 /// heap.push(2);
45125 /// assert_eq!(heap.peek(), Some(&5));
45137 /// Returns the number of elements the binary heap can hold without reallocating.
45145 /// let mut heap = BinaryHeap::with_capacity(100);
45146 /// assert!(heap.capacity() >= 100);
45147 /// heap.push(4);
45171 /// let mut heap = BinaryHeap::new();
45172 /// heap.reserve_exact(100);
45173 /// assert!(heap.capacity() >= 100);
45174 /// heap.push(4);
45196 /// let mut heap = BinaryHeap::new();
45197 /// heap.reserve(100);
45198 /// assert!(heap.capacity() >= 100);
45199 /// heap.push(4);
45214 /// let mut heap: BinaryHeap<i32> = BinaryHeap::with_capacity(100);
45216 /// assert!(heap.capacity() >= 100);
45217 /// heap.shrink_to_fit();
45218 /// assert!(heap.capacity() == 0);
45237 /// let mut heap: BinaryHeap<i32> = BinaryHeap::with_capacity(100);
45239 /// assert!(heap.capacity() >= 100);
45240 /// heap.shrink_to(10);
45241 /// assert!(heap.capacity() >= 10);
45261 /// let heap = BinaryHeap::from(vec![1, 2, 3, 4, 5, 6, 7]);
45263 /// io::sink().write(heap.as_slice()).unwrap();
45279 /// let heap = BinaryHeap::from(vec![1, 2, 3, 4, 5, 6, 7]);
45280 /// let vec = heap.into_vec();
45292 /// Returns the length of the binary heap.
45300 /// let heap = BinaryHeap::from(vec![1, 3]);
45302 /// assert_eq!(heap.len(), 2);
45310 /// Checks if the binary heap is empty.
45318 /// let mut heap = BinaryHeap::new();
45320 /// assert!(heap.is_empty());
45322 /// heap.push(3);
45323 /// heap.push(5);
45324 /// heap.push(1);
45326 /// assert!(!heap.is_empty());
45333 /// Clears the binary heap, returning an iterator over the removed elements.
45343 /// let mut heap = BinaryHeap::from(vec![1, 3]);
45345 /// assert!(!heap.is_empty());
45347 /// for x in heap.drain() {
45351 /// assert!(heap.is_empty());
45359 /// Drops all items from the binary heap.
45367 /// let mut heap = BinaryHeap::from(vec![1, 3]);
45369 /// assert!(!heap.is_empty());
45371 /// heap.clear();
45373 /// assert!(heap.is_empty());
45679 /// Removes heap elements in heap order.
45728 let mut heap = BinaryHeap { data: vec };
45729 heap.rebuild();
45730 heap
45740 fn from(heap: BinaryHeap<T>) -> Vec<T> {
45741 heap.data
45758 /// the binary heap in arbitrary order. The binary heap cannot be used
45767 /// let heap = BinaryHeap::from(vec![1, 2, 3, 4]);
45770 /// for x in heap.into_iter() {
46809 //! A contiguous growable array type with heap-allocated contents, written
47090 /// If a `Vec` *has* allocated memory, then the memory it points to is on the heap
47098 /// pointer to the head of the allocation in the heap, length and capacity.
47099 /// The bottom part is the allocation on the heap, a contiguous memory block.
49610 /// the existing heap allocation.
50171 //! A pointer type for heap allocation.
50174 //! heap allocation in Rust. Boxes provide ownership for this allocation, and
50180 //! Move a value from the stack to the heap by creating a [`Box`]:
50329 /// A pointer type for heap allocation.
50341 /// Allocates memory on the heap and then places `x` into it.
50415 /// Allocates memory on the heap then places `x` into it,
50434 /// Constructs a new box with uninitialized contents on the heap,
50462 /// being filled with `0` bytes on the heap
50674 /// This conversion does not allocate on the heap and happens in place.
51156 /// This conversion does not allocate on the heap and happens in place.
51359 /// The conversion allocates on the heap and moves `t`
51381 /// This conversion does not allocate on the heap and happens in place.
51391 /// This conversion allocates on the heap
51427 /// This conversion allocates on the heap
51456 /// This conversion does not allocate on the heap and happens in place.
51481 /// This conversion moves the array to newly heap-allocated memory.