Collection Adapters and Specialized Types

Heap Construction and Extraction

BinaryHeap<T> supports $O(n)$ bulk construction from an existing vector or array (BinaryHeap::from(vec)) and zero-reallocation conversions back into a Vec<T>—either in arbitrary heap-array order ($O(1)$ via .into_vec()) or in ascending sorted order ($O(n \log n)$ via .into_sorted_vec()).

Bulk Construction: $O(n)$ From<Vec<T>> vs. $O(n \log n)$ Repeated push()

Pushing $n$ elements one at a time into an empty BinaryHeap takes $O(n \log n)$ worst-case time. By contrast, constructing a BinaryHeap in bulk via BinaryHeap::from(vec) or .collect::<BinaryHeap<T>>() reuses the Vec<T> allocation in place and runs Floyd's bottom-up heapify algorithm (rebuild), which sifts down only the non-leaf nodes (0..len / 2) in $O(n)$ linear time:

Floyd's Bottom-Up Heapify on [20, 80, 50, 90, 60] (n = 5):
  - Leaves at indices 2..5 ([50, 90, 60]) are already valid 1-element heaps
  - Sift down index 1 (80 vs children 90, 60) -> swaps 80 and 90
  - Sift down index 0 (20 vs children 90, 50) -> swaps 20 -> 90 -> 80
  Total work across all levels: sum_{h=0}^{log n} (n / 2^{h+1}) * O(h) = O(n)!

use std::collections::BinaryHeap;

fn main() {
    let raw_vec = vec![20, 80, 50, 90, 60];
    let vec_ptr = raw_vec.as_ptr();

    // O(n) in-place heap construction reusing `raw_vec`'s heap buffer:
    let heap = BinaryHeap::from(raw_vec);

    println!("Max element: {:?}", heap.peek());
    println!(
        "Reused allocation in place: {}",
        heap.as_slice().as_ptr() == vec_ptr
    );
}

Max element: Some(&90)
Reused allocation in place: true

Extracting Elements from a BinaryHeap<T>

Method Return Type Time Complexity Element Order
heap.into_vec() (or Vec::from(heap)) Vec<T> $O(1)$ (zero copy) Arbitrary heap-array order
heap.into_sorted_vec() Vec<T> $O(n \log n)$ (in-place heapsort) Ascending sorted order (v[0] is smallest)
while let Some(x) = heap.pop() T (one by one) $O(k \log n)$ for $k$ pops Descending sorted order (largest first)
heap.drain() Drain<'_, T> $O(n)$ Arbitrary heap-array order (retains capacity) 
use std::collections::BinaryHeap;

fn main() {
    let heap = BinaryHeap::from([40, 10, 90, 30, 70]);

    // Consumes the heap and performs an in-place heapsort into an ascending Vec<i32>:
    let sorted_asc: Vec<i32> = heap.into_sorted_vec();
    println!("into_sorted_vec (ascending): {sorted_asc:?}");
}

into_sorted_vec (ascending): [10, 30, 40, 70, 90]

Merging Two Heaps with append(&mut other)

Calling heap_a.append(&mut heap_b) moves all elements from heap_b into heap_a's backing Vec<T> and rebuilds the heap invariant in $O(|a| + |b|)$ (or $O(|b| \log(|a| + |b|))$ when $|b| \ll |a|$), leaving heap_b empty.