`BinaryHeap::into_sorted_vec` în Rust

BinaryHeap și Reverse: cozi de priorități Rust 1.5

Consumă heap-ul și returnează un Vec cu toate elementele sortate crescător.

Sintaxă

pub fn into_sorted_vec(self) -> Vec<T>

Ce face `BinaryHeap::into_sorted_vec`

into_sorted_vec() transformă heap-ul într-un vector sortat crescător (de la cel mai mic la cel mai mare), deși pop le-ar fi dat în ordine descrescătoare. Heap-ul este consumat.

Dacă vrei elementele fără sortare, into_vec() e mai rapid și le dă în ordinea internă. Pentru „primele K cele mai mari” dintr-o listă lungă, un heap mic cu Reverse și into_sorted_vec la final este o soluție eficientă.

Ce returnează

Un Vec<T> sortat crescător.

Exemple

Exemplul 1: Din heap în vector sortat

use std::collections::BinaryHeap;

fn main() {
    let mut heap = BinaryHeap::new();
    heap.extend([40, 10, 30, 20, 50]);
    let sortat = heap.into_sorted_vec();
    println!("{:?}", sortat);
}

Rezultat

[10, 20, 30, 40, 50]

Exemplul 2: Cele mai mari 3 scoruri dintr-o listă lungă

Ținem un heap de cel mult 3 elemente învelite în Reverse: vârful este cel mai mic dintre primele 3 și iese când apare un scor mai mare. into_sorted_vec sortează crescător după Reverse, adică descrescător după scor.

use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn main() {
    let scoruri = [72, 95, 61, 88, 99, 54, 91, 83];
    let mut top = BinaryHeap::new();
    for s in scoruri {
        top.push(Reverse(s));
        if top.len() > 3 {
            top.pop();
        }
    }
    let mut cele_mai_mari: Vec<u32> = top.into_sorted_vec().into_iter().map(|Reverse(s)| s).collect();
    println!("{:?}", cele_mai_mari);
    cele_mai_mari.sort();
    println!("crescător: {:?}", cele_mai_mari);
}