Module 4Priority Queue (BinaryHeap)Lesson 18 of 2320 min

BinaryHeap Max-Heap

push, pop, peek — largest first.

BinaryHeap is a max-heap

rust

use std::collections::BinaryHeap;

fn main() {
    let mut h = BinaryHeap::new();
    h.push(3);
    h.push(10);
    h.push(5);
    println!("peek={:?}", h.peek());
    println!("pop={:?}", h.pop());
    println!("pop={:?}", h.pop());
    println!("pop={:?}", h.pop());
}

Output

peek=Some(10)
pop=Some(10)
pop=Some(5)
pop=Some(3)

peek

rust

h.peek() // Option<&T>

Interview uses

Repeatedly take largest

Huffman / event simulation

Combine with custom Ord types

Complexity

push/pop O(log n), peek O(1).

Challenge

Push pairs (priority, id) and pop highest priority.

Tips

Max-heap default
pop returns Option
peek does not remove

Try it live

BinaryHeap Max-HeapRust 2021

Loading editor…

Output

Press Run to compile and execute.