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.
A maxheap implementation. This will have the largest item as the top of the heap. * * Note: always pass by reference when modifying a heap. *
A minheap implementation. This will have the smallest item as the top of the heap. * * Note: always pass by reference when modifying a heap. *