Класс BinaryHeap
Класс BinaryHeap представляет собой двоичную кучу - структуру данных,
которая позволяет эффективно хранить элементы и извлекать максимальный
элемент за логарифмическое время. По умолчанию куча является max-heap,
то есть на вершине всегда находится наибольший элемент. Для использования
класса необходимо подключить модуль std::collections::BinaryHeap.
Элементы должны реализовывать типажи Ord и Clone.
Основные методы класса: new создаёт пустую кучу,
push добавляет элемент, pop извлекает максимальный элемент,
peek возвращает ссылку на максимальный элемент без удаления.
Синтаксис
use std::collections::BinaryHeap;
let heap: BinaryHeap<T> = BinaryHeap::new();
Пример
Давайте создадим пустую кучу и добавим в неё несколько чисел:
use std::collections::BinaryHeap;
fn main()
{
let mut heap: BinaryHeap<i32> = BinaryHeap::new();
heap.push(3);
heap.push(1);
heap.push(4);
heap.push(1);
heap.push(5);
println!("{:?}", heap);
}
Результат выполнения кода:
[5, 3, 4, 1, 1]
Пример
Давайте извлечём максимальный элемент из кучи с помощью метода pop:
use std::collections::BinaryHeap;
fn main()
{
let mut heap: BinaryHeap<i32> = BinaryHeap::new();
heap.push(3);
heap.push(1);
heap.push(4);
heap.push(1);
heap.push(5);
let max = heap.pop();
println!("{:?}", max);
println!("{:?}", heap);
}
Результат выполнения кода:
Some(5)
[4, 3, 1, 1]
Пример
Давайте посмотрим на максимальный элемент без удаления с помощью метода peek:
use std::collections::BinaryHeap;
fn main()
{
let mut heap: BinaryHeap<i32> = BinaryHeap::new();
heap.push(3);
heap.push(1);
heap.push(4);
heap.push(1);
heap.push(5);
let max = heap.peek();
println!("{:?}", max);
println!("{:?}", heap);
}
Результат выполнения кода:
Some(5)
[5, 3, 4, 1, 1]
Пример
Давайте создадим кучу из вектора с помощью метода from:
use std::collections::BinaryHeap;
fn main()
{
let vec = vec![1, 2, 3, 4, 5];
let heap = BinaryHeap::from(vec);
println!("{:?}", heap);
}
Результат выполнения кода:
[5, 4, 3, 1, 2]
