tango.util.container.more.Heap

License:

Version:

Author:

struct Heap(T, alias Compare = minHeapCompare!(T), alias Move = defaultHeapSwap!(T)) ¶

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.

void push(T t) ¶

Inserts the given element into the heap.

void push(T[] array) ¶

Inserts all elements in the given array into the heap.

T pop() ¶

Removes the top of this heap and returns it.

void removeAll(T t) ¶

Remove the every instance that matches the given item.

bool remove(T t) ¶

Remove the first instance that matches the given item.

Returns:

true iff the item was found, otherwise false.

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.

T peek() ¶

Gets the value at the top of the heap without removing it.

size_t size() [@property, const] ¶

Returns the number of elements in this heap.

void clear() ¶

Reset this heap.

void clear(T[] host) ¶

reset this heap, and use the provided host for value elements

size_t capacity() [const] ¶

Get the reserved capacity of this heap.

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.

Heap clone() ¶

Return a shallow copy of this heap.

template MinHeap(T) ¶

A minheap implementation. This will have the smallest item as the top of the heap.

Note:

always pass by reference when modifying a heap.

template MaxHeap(T) ¶

A maxheap implementation. This will have the largest item as the top of the heap.

Note:

always pass by reference when modifying a heap.