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, uint). * 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)

) {

import ocean.core.Verify;;

alias remove = pop;

template opOpAssign(string op : "~");

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

void clear();

void clear(T[] host);

size_t capacity();

uint capacity(uint value);

Heap clone();

}

Members

Aliases

remove alias remove = pop: Undocumented in source.

Functions

capacity size_t capacity(): Get the reserved capacity of this heap.
capacity uint capacity(uint 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.
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.
size size_t size(): Returns the number of elements in this heap.

Templates

opOpAssign template opOpAssign(string op : "~"): Undocumented in source.

Heap

Members

Aliases

Functions

Templates

Meta

Source