Heap package:vector-algorithms

This module implements operations for working with a quaternary heap stored in an unboxed array. Most heapsorts are defined in terms of a binary heap, in which each internal node has at most two children. By contrast, a quaternary heap has internal nodes with up to four children. This reduces the number of comparisons in a heapsort slightly, and improves locality (again, slightly) by flattening out the heap.

Given a heap stored in a portion of an array [l,u) and an element e, inserts the element into the heap, resulting in a heap in [l,u]. Note: it is best to only use this operation when incremental construction of a heap is required. heapify is capable of building a heap in O(n) time, while repeated insertion takes O(n*log n) time.

Constructs a heap in a portion of an array [l, u), using the values therein. Note: heapify is more efficient than constructing a heap by repeated insertion. Repeated insertion has complexity O(n*log n) while heapify is able to construct a heap in O(n), where n is the number of elements in the heap.

Given a heap stored in a portion of an array [l,u), sorts the highest values into [m,u). The elements in [l,m) are not in any particular order.