BinaryHeap în Rust

use std::collections::BinaryHeap;

let mut h: BinaryHeap<T> = BinaryHeap::new();
pub fn push(&mut self, item: T)
pub fn pop(&mut self) -> Option<T>
pub fn peek(&self) -> Option<&T>

Ce face BinaryHeap

BinaryHeap<T> ține elementele astfel încât cel mai mare să fie mereu disponibil imediat. push adaugă un element, pop scoate și returnează cel mai mare (Option<T>, None când e gol), iar peek doar îl arată. Ambele operații de modificare sunt rapide (logaritmice).

Este structura potrivită pentru „procesează întâi ce e mai important”: sarcini cu prioritate, evenimente ordonate în timp, algoritmul lui Dijkstra, primele K valori dintr-un flux. Elementele trebuie să implementeze Ord; tuplurile (prioritate, date) se compară întâi după prioritate.

Implicit este un max-heap. Pentru a scoate întâi cel mai mic element, învelește valorile în std::cmp::Reverse. Parcurgerea cu iter() sau afișarea cu {:?} nu sunt în ordine sortată; pentru ordine, scoate cu pop sau folosește into_sorted_vec.

Parametri

Parametru	Descriere
item	Elementul adăugat (la push).

Ce returnează

pop: Option<T>. peek: Option<&T>. push: nimic.

Exemple

Exemplul 1: Cel mai mare iese primul

use std::collections::BinaryHeap;

fn main() {
    let mut heap = BinaryHeap::new();
    for n in [5, 1, 8, 3, 9, 2] {
        heap.push(n);
    }
    println!("cel mai mare (peek): {:?}", heap.peek());
    println!("len = {}", heap.len());
    while let Some(n) = heap.pop() {
        print!("{n} ");
    }
    println!();
}

Rezultat

cel mai mare (peek): Some(9)
len = 6
9 8 5 3 2 1

Exemplul 2: Sarcini cu prioritate

use std::collections::BinaryHeap;

fn main() {
    let mut sarcini = BinaryHeap::new();
    sarcini.push((2, "răspunde la emailuri"));
    sarcini.push((5, "repară serverul"));
    sarcini.push((1, "udă florile"));
    sarcini.push((3, "trimite factura"));
    while let Some((prioritate, sarcina)) = sarcini.pop() {
        println!("[{prioritate}] {sarcina}");
    }
}

Rezultat

[5] repară serverul
[3] trimite factura
[2] răspunde la emailuri
[1] udă florile

Exemplul 3: Afișarea directă nu e sortată

{:?} arată ordinea internă a heap-ului: doar primul element (maximul) are o poziție garantată.

use std::collections::BinaryHeap;

fn main() {
    let heap = BinaryHeap::from(vec![3, 1, 4, 1, 5, 9, 2, 6]);
    println!("intern:      {:?}", heap);
    println!("peek:        {:?}", heap.peek());
    println!("sortat:      {:?}", heap.into_sorted_vec());
}

Rezultat

intern:      [9, 6, 4, 1, 5, 3, 2, 1]
peek:        Some(9)
sortat:      [1, 1, 2, 3, 4, 5, 6, 9]

Greșeli frecvente

• Te aștepți ca pop să scoată cel mai mic element: implicit scoate cel mai mare. Folosește Reverse pentru min-heap.
• Te bazezi pe ordinea din iter() sau {:?}: nu este sortată.
• Pui f64 direct în heap: f64 nu implementează Ord. Folosește întregi (de exemplu bani sau milisecunde) sau un tip propriu cu Ord.

Comenzi înrudite

• BinaryHeap::into_sorted_vec: Consumă heap-ul și returnează un Vec cu toate elementele sortate crescător.
• Reverse: Învelitoare care inversează ordinea unei valori: transformă BinaryHeap în min-heap și sortează descrescător după cheie.
• VecDeque: Coada cu două capete: adaugă și scoate rapid elemente atât la început, cât și la sfârșit.
• BTreeSet::first: Returnează cel mai mic (first) sau cel mai mare (last) element al mulțimii sortate; None dacă e goală.