HeapOps

Heap operations for random-access ranges

Members

Aliases

lessFun
alias lessFun = naryFun!less
Undocumented in source.

Functions

buildHeap
void buildHeap(Range r)

template because of @@@12410@@@

heapSort
void heapSort(Range r)

template because of @@@12410@@@

isHeap
bool isHeap(Range r)
percolate
void percolate(Range r, size_t parent, size_t end)

Alternate version of siftDown that performs fewer comparisons, see https://en.wikipedia.org/wiki/Heapsort#Bottom-up_heapsort. The percolate process first sifts the parent all the way down (without comparing it against the leaves), and then a bit up until the heap property is restored. So there are more swaps but fewer comparisons. Gains are made when the final position is likely to end toward the bottom of the heap, so not a lot of sifts back are performed. template because of @@@12410@@@

siftDown
void siftDown(Range r, size_t parent, size_t end)

Sifts down rparent (which is initially assumed to be messed up) so the heap property is restored for r[parent .. end]. template because of @@@12410@@@

Meta