Heap

A heap is a data structure where you can insert items in random order and extract them in sorted order. * Pushing an element into the heap takes O(lg n) and popping the top of the heap takes O(lg n). Heaps are * thus popular for sorting, among other things. * * No opApply is provided, since most people would expect this to return the contents in sorted order, * not do significant heap allocation, not modify the collection, and complete in linear time. This * combination is not possible with a heap. * * Note: always pass by reference when modifying a heap. * * The template arguments to the heap are: * T = the element type * Compare = a function called when ordering elements. Its signature should be bool(T, T). * see minHeapCompare() and maxHeapCompare() for examples. * Move = a function called when swapping elements. Its signature should be void(T, size_t). * The default does nothing, and should suffice for most users. You * probably want to keep this function small; it's called O(log N) * times per insertion or removal.

struct Heap (

alias Compare = minHeapCompare!(T)

alias Move = defaultHeapSwap!(T)

) {

void push(T t);

void push(T[] array);

T pop();

void removeAll(T t);

bool remove(T t);

T removeAt(size_t index);

T peek();

size_t size [@property getter];

void clear();

void clear(T[] host);

size_t capacity();

size_t capacity(size_t value);

Heap clone();

alias remove = pop;

void opOpAssign(T t);

void opOpAssign(T[] array);

}

Members

Aliases

remove alias remove = pop: Undocumented in source.

Functions

capacity size_t capacity(): Get the reserved capacity of this heap.
capacity size_t capacity(size_t value): Reserve enough space in this heap for value elements. The reserved space is truncated or extended as necessary. If the value is less than the number of elements already in the heap, throw an exception.
clear void clear(): Reset this heap.
clear void clear(T[] host): reset this heap, and use the provided host for value elements
clone Heap clone(): Return a shallow copy of this heap.
opOpAssign void opOpAssign(T t): Undocumented in source. Be warned that the author may not have intended to support it.
opOpAssign void opOpAssign(T[] array): Undocumented in source. Be warned that the author may not have intended to support it.
peek T peek(): Gets the value at the top of the heap without removing it.
pop T pop(): Removes the top of this heap and returns it.
push void push(T t): Inserts the given element into the heap.
push void push(T[] array): Inserts all elements in the given array into the heap.
remove bool remove(T t): Remove the first instance that matches the given item. * Returns: true iff the item was found, otherwise false.
removeAll void removeAll(T t): Remove the every instance that matches the given item.
removeAt T removeAt(size_t index): Remove the element at the given index from the heap. * The index is according to the heap's internal layout; you are * responsible for making sure the index is correct. * The heap invariant is maintained.

Properties

size size_t size [@property getter]: Returns the number of elements in this heap.

Heap

Members

Aliases

Functions

Properties

Meta

Source