Функция new класса BinaryHeap

Функция new класса BinaryHeap создаёт новую пустую двоичную кучу. Двоичная куча - это структура данных, в которой наибольший элемент всегда находится на вершине. По умолчанию это max-heap, то есть куча упорядочена так, что наибольший элемент извлекается первым. Функция не принимает параметров и возвращает экземпляр BinaryHeap с нулевой ёмкостью.

Для создания кучи с заранее выделенной ёмкостью используйте with_capacity. Для добавления элементов применяйте push, а для извлечения наибольшего - pop или peek.

Синтаксис

BinaryHeap::new()

Пример

Давайте создадим пустую двоичную кучу и проверим, что она пуста:

use std::collections::BinaryHeap;

fn main()
{
	let heap: BinaryHeap<i32> = BinaryHeap::new();
	println!("is empty: {}", heap.is_empty());
	println!("length: {}", heap.len());
}

Результат выполнения кода:

is empty: true
length: 0

Пример

Давайте создадим кучу, добавим в неё несколько чисел и извлечём наибольший элемент:

use std::collections::BinaryHeap;

fn main()
{
	let mut heap: BinaryHeap<i32> = BinaryHeap::new();
	heap.push(3);
	heap.push(1);
	heap.push(4);
	heap.push(2);

	println!("{:?}", heap);
	println!("peek: {:?}", heap.peek());
	println!("pop: {:?}", heap.pop());
	println!("after pop: {:?}", heap);
}

Результат выполнения кода:

[4, 2, 3, 1]
peek: Some(4)
pop: Some(4)
after pop: [3, 2, 1]

Пример

Давайте создадим кучу из строк и извлечём наибольшую строку в лексикографическом порядке:

use std::collections::BinaryHeap;

fn main()
{
	let mut heap: BinaryHeap<&str> = BinaryHeap::new();
	heap.push("abcde");
	heap.push("12345");
	heap.push("bcd");

	println!("peek: {:?}", heap.peek());
	println!("pop: {:?}", heap.pop());
	println!("pop: {:?}", heap.pop());
}

Результат выполнения кода:

peek: Some("bcd")
pop: Some("bcd")
pop: Some("abcde")

Смотрите также

класс BinaryHeap,
который представляет двоичную кучу
метод push,
который добавляет элемент в кучу
метод pop,
который извлекает наибольший элемент из кучи
метод peek,
который возвращает ссылку на наибольший элемент без извлечения