BinaryHeap<T>

BinaryHeap<T> (std::collections::BinaryHeap<T>) is a priority queue adapter implemented as an implicit binary max-heap stored inside a single contiguous Vec<T>, ensuring the greatest element (according to T: Ord) is always at index 0.

Implicit Tree-in-Array Representation

Instead of allocating heap nodes with parent/left/right pointers, a binary heap packs a complete binary tree level-by-level into a flat Vec<T>. For any element at zero-based index $i$:

• Parent index: $(i - 1) / 2$ (for $i > 0$)
• Left child index: $2i + 1$
• Right child index: $2i + 2$

             100 (idx 0)
            /           \
       80 (idx 1)     60 (idx 2)
        /      \        /
   40 (idx 3) 50 (4)  20 (idx 5)

Backing Vec<i32>:
+-----+-----+-----+-----+-----+-----+
| 100 |  80 |  60 |  40 |  50 |  20 |
+-----+-----+-----+-----+-----+-----+
  [0]   [1]   [2]   [3]   [4]   [5]

The Heap Property vs. Full Sorted Order

A BinaryHeap<T> maintains only the max-heap invariant: every parent is $\ge$ its two children (v[i] >= v[2*i + 1] and v[i] >= v[2*i + 2]). Sibling and cousin nodes have no required relative order between them (for example, 60 at index 2 can have children smaller than 80's children).

Because the backing array is only partially ordered:

• heap.peek() is guaranteed to return the maximum element &v[0] in $O(1)$ time.
• heap.pop() removes and returns elements in descending sorted order ($O(\log n)$ per pop).
• heap.iter() scans the backing Vec<T> from index 0 to len - 1 in arbitrary heap-array order, not sorted order!

use std::collections::BinaryHeap;

fn main() {
    let mut heap = BinaryHeap::from([40, 100, 20, 80, 50, 60]);

    println!("Max at root (.peek()): {:?}", heap.peek());

    print!("Popping in descending order: ");
    while let Some(top) = heap.pop() {
        print!("{top} ");
    }
    println!();
}

Max at root (.peek()): Some(&100)
Popping in descending order: 100 80 60 50 40 20