The OpenD Programming Language

HeapOps

Heap operations for random-access ranges

template HeapOps (

alias less

Range

) {

template hasSwappableElements(R) via import std.range.primitives : hasSwappableElements, hasAssignableElements;;

enum bool hasAssignableElements(R); via import std.range.primitives : hasSwappableElements, hasAssignableElements;;

void swapAt(R r, size_t i1, size_t i2) via import std.algorithm.mutation : swapAt;;

void heapSort(Range r);

void buildHeap(Range r);

bool isHeap(Range r);

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

void percolate(Range r, size_t parent, size_t end);

}

Members

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

Source

See Implementation

mir container binaryheap functions

heapify

structs

BinaryHeap

templates

HeapOps