std.container.binaryheap

Этот модуль предоставляет адаптер BinaryHeap (также известный как очередь с приоритетами), который преобразует произвольный диапазон с произвольным доступом, предоставленный пользователем, в бинарную кучу.

Этот модуль является подмодулем std.container.

Исходный код

std/container/binaryheap.d

Лицензия:

Распространяется по лицензии Boost Software License, версия 1.0. (См. прилагаемый файл LICENSE_1_0.txt или копию по адресу boost.org/LICENSE_1_0.txt).

Авторы:

Andrei Alexandrescu

Примеры:

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]));

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 определяет так называемую кучу максимумов, которая оптимизирует извлечение наибольших элементов. Для определения кучи минимумов необходимо создать BinaryHeap с "a > b" в качестве своего предиката.

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

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

Примеры:

Пример из "Введения в алгоритмы" Кормен и др., стр. 146

import std.algorithm.comparison : equal;
int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
auto h = heapify(a);
// largest element
writeln(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();

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

@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.

Примеры:

import std.conv : to;
import std.range.primitives;
{
    // example from "Introduction to Algorithms" Cormen et al., p 146
    int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
    auto h = heapify(a);
    h = heapify!"a < b"(a);
    writeln(h.front); // 16
    writeln(a); // [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
    auto witness = [ 16, 14, 10, 9, 8, 7, 4, 3, 2, 1 ];
    for (; !h.empty; h.removeFront(), witness.popFront())
    {
        assert(!witness.empty);
        writeln(witness.front); // h.front
    }
    assert(witness.empty);
}
{
    int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
    int[] b = new int[a.length];
    BinaryHeap!(int[]) h = BinaryHeap!(int[])(b, 0);
    foreach (e; a)
    {
        h.insert(e);
    }
    writeln(b); // [16, 14, 10, 8, 7, 3, 9, 1, 4, 2]
}