std.container.binaryheap

import std.algorithm.comparison : equal;
import std.range : take;
auto maxHeap = heapify([4, 7, 3, 1, 5]);
assert(maxHeap.take(3).equal([7, 5, 4]));

auto minHeap = heapify!"a > b"([4, 7, 3, 1, 5]);
assert(minHeap.take(3).equal([1, 3, 4]));

Переместиться к: acquire · assume · capacity · clear · conditionalInsert · conditionalSwap · dup · empty · front · insert · length · popFront · release · removeAny · removeFront · replaceFront · this

struct BinaryHeap(Store, alias less = "a < b") if (isRandomAccessRange!Store || isRandomAccessRange!(typeof(Store.init[])));

Реализует контейнер двоичной кучи поверх данного типа дипазона с произвольным доступом (обычно T[]) или типа контейнера с произвольным доступом (обычно Array!T). Документация BinaryHeap ссылается на нижележащий диапазон или контейнер как на место хранения кучи.

Двоичная куча порождает структуру над нижележащим хранилищем так, что получение доступпа к наибольшему элементу (используя свойство front) – операция со сложностью Ο(1), а его извлечение (с использованием метода removeFront()) выполняется за время Ο(log n).

Если less – оператор меньше-чем, который является вариантом по-умолчанию, тогда BinaryHeap определяет так называемую max-кучу, которая оптимизирует извлечение самых больших элементов. Для того, чтобы определить min-кучу, создайте экземпляр BinaryHeap с предикатом "a > b".

Простое извлечение элементов из контейнера BinaryHeap равносильно ленивому выбору элементов хранилища Store в нисходящем порядке. Извлечение элементов из BinaryHeap до завершения оставляет нижележащее хранилище отсортированным в возрастающем порядке, но, снова, выдаёт элементы в нисходящем порядке.

Если Store является диапазоном, BinaryHeap не может возрастать за пределы этого диапазона. Если Store является контейнером, который поддерживает insertBack, BinaryHeap может увеличиваться, добавляя элементы к контейнеру.

Примеры:

Пример из "Introduction to Algorithms" Cormen et al, страница 146

import std.algorithm.comparison : equal;
int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
auto h = heapify(a);
// наибольший элемент
assert(h.front == 16);
// a has the heap property
assert(equal(a, [ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]));

Примеры:

BinaryHeap реализует стандартный интерфейс входного диапазона, позволяющий лениво итерировать нижележащий диапазон в нисходящем порядке.

import std.algorithm.comparison : equal;
import std.range : take;
int[] a = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7];
auto top5 = heapify(a).take(5);
assert(top5.equal([16, 14, 10, 9, 8]));

this(Store s, size_t initialSize = size_t.max);

Преобразует хранилище s в кучу. Если задан initialSize, то только первые initialSize элементов из s преобразуются в кучу, после чего куча может вырастать до r.length (если Store является диапазоном) или неограниченно (если Store является контейнером с insertBack). Выполняется за Ο(min(r.length, initialSize)) вычислений less.

void acquire(Store s, size_t initialSize = size_t.max);

Становится владельцем хранилища. После этого, манипуляции с s могут привести к тому, что куча станет работать некорректно.

void assume(Store s, size_t initialSize = size_t.max);

Становится владельцем хранилища, исходя из того, что оно уже было организовано как куча.

auto release();

Очищает кучу. Возвращает часть хранилища от 0 до length, которая удовлетворяет свойству кучи.

@property bool empty();

Возвращает true, если куча пуста, false в противном случае.

@property BinaryHeap dup();

Возвращает дубликат кучи. Метод dup доступен, только если нижележащее хранилище поддерживает его.

@property size_t length();

Возвращает длину кучи.

@property size_t capacity();

Возвращает возможность кучи, которая равна длине нижележащего хранилища (если хранилище является диапазоном), или capacity нижележащего хранилища (если оно является контейнером).

@property ElementType!Store front();

Возвращает копию переднего элемента кучи, который является самым большим элементом согласно предикату less.

void clear();

Очищает кучу, отделяя её от нижележащего хранилища.

size_t insert(ElementType!Store value);

Вставляет значение value в хранилище. Если нижележащее хранилище является диапазоном и length == capacity, метод бросает исключение.

void removeFront();

alias popFront = removeFront;

Удаляет наибольший элемент из кучи.

ElementType!Store removeAny();

Удаляет наибольший элемент из кучи и возвращает его копию. Элемент всё еще будет находиться в хранилище кучи. Из соображений производительности вы можете использовать removeFront с кучей объектов, которые являются дорогостоящими для копирования.

void replaceFront(ElementType!Store value);

Заменяет самый большой элемент в хранилище значением value.

bool conditionalInsert(ElementType!Store value);

Если куча имеет место для роста, вставляет value в хранилище и возвращает true. В противном случае, если less(value, front), вызывает replaceFront(value) и снова возвращает true. В противном случае, оставляет кучу нетронутой и возвращает false. Этот метод полезен в сценариях, когда необходимо собрать наименьшие k элементов из набора кандидатов.

bool conditionalSwap(ref ElementType!Store value);

Обмен допустим, если куча полная. Если less(value, front), метод меняет store.front и value и возвращает true. В противном случае, он оставляет кучу нетронутой и возвращает false.

BinaryHeap!(Store, less) heapify(alias less = "a < b", Store)(Store s, size_t initialSize = size_t.max);

Удобная функция, которая возвращает объект BinaryHeap!Store, инициализированный с s и initialSize.