module std.arrayheap

This module provides mutable heaps (efficiently stored in an array, hence the name). It also exports a decent sorting algorithm.

• (arrayheap-new cmp) creates a new, empty arrayheap, with comparator cmp (see module std.map for a description of comparators).
• (arrayheap? heap) returns true if heap is an arrayheap.
• (arrayheap-len heap) returns the number of elements in arrayheap heap in O(1).
• (arrayheap-empty? heap) checks whether the arrayheap heap is empty.
• (arrayheap-insert! heap key) inserts the key into arrayheap heap in O(log n) time.
• (arrayheap-minimum heap) returns the minimum key in heap in time O(1) or panics if the heap is empty.
• (arrayheap-remove-minimum! heap) removes and returns the minimum key in heap or panics if the heap is empty. Time complexity is O(log n).
• (arrayheap-from-array cmp array) creates a new arrayheap with comparator cmp and keys from array. The array is copied, so it can be freely disposed of afterwards. The time needed is O(n).
• (heapsort! cmp array) orders array in place, comparing the elements with cmp. Time complexity is O(n log n).