Переместиться к: BinaryHeap · heapify
Исходный код: std/container/binaryheap.d
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
BinaryHeap
(Store, alias less = "a < b") if (isRandomAccessRange!Store || isRandomAccessRange!(typeof(Store.init[])));
BinaryHeap
ссылается на нижележащий диапазон или контейнер как на место хранения кучи.
BinaryHeap
определяет так называемую max-кучу, которая оптимизирует извлечение самых больших элементов. Для того, чтобы определить min-кучу, создайте экземпляр BinaryHeap
с предикатом "a > b".
Простое извлечение элементов из контейнера BinaryHeap
равносильно ленивому выбору элементов хранилища Store в нисходящем порядке. Извлечение элементов из BinaryHeap
до завершения оставляет нижележащее хранилище отсортированным в возрастающем порядке, но, снова, выдаёт элементы в нисходящем порядке.
Если Store является диапазоном, BinaryHeap
не может возрастать за пределы этого диапазона. Если Store является контейнером, который поддерживает insertBack, BinaryHeap
может увеличиваться, добавляя элементы к контейнеру.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]));
s
, size_t initialSize
= size_t.max);
s
в кучу. Если задан initialSize
, то только первые initialSize
элементов из s
преобразуются в кучу, после чего куча может вырастать до r.length (если Store является диапазоном) или неограниченно (если
Store является контейнером с insertBack). Выполняется за
Ο(min(r.length, initialSize
)) вычислений less.acquire
(Store s
, size_t initialSize
= size_t.max);
s
могут привести к тому, что куча станет работать некорректно.assume
(Store s
, size_t initialSize
= size_t.max);
release
();
empty
();
true
, если куча пуста, false
в противном случае.dup
();
dup
доступен, только если нижележащее хранилище поддерживает его.length
();
capacity
();
front
();
clear
();
insert
(ElementType!Store value
);
value
в хранилище. Если нижележащее хранилище является диапазоном и length == capacity, метод бросает исключение.removeFront
();
popFront
= removeFront;
removeAny
();
replaceFront
(ElementType!Store value
);
value
.conditionalInsert
(ElementType!Store value
);
value
в хранилище и возвращает true
. В противном случае, если less(value
, front), вызывает replaceFront(value
) и снова возвращает true
. В противном случае, оставляет кучу нетронутой и возвращает false
. Этот метод полезен в сценариях, когда необходимо собрать наименьшие k элементов из набора кандидатов.conditionalSwap
(ref ElementType!Store value
);
value
, front), метод меняет store.front и value
и возвращает true
. В противном случае, он оставляет кучу нетронутой и возвращает false
.heapify
(alias less = "a < b", Store)(Store s
, size_t initialSize
= size_t.max);
s
и initialSize
.