Possible TODOs for binary heap

[fingolfin]

• should its functions also get a DT_ resp. _DT_ prefix?
• when I wrote it, it was convenient to represent the heap as a record, as my prototype was written in GAP, which I then gradually converted to C. Perhaps we'd be better off rewriting this into a position object, though...
• add a "decrease key" function?
• add a "merge" function which merges two heaps
• there is a simple optimization I'd want to consider: if the user does not specify an isLess, or specifies LT resp. \<; then detect that and do not invoke CALL_2ARGS(isLess, ELM_PLIST(data, right), ELM_PLIST(data, left)), instead use LtFuncs, for better performance.
• perhaps also use C++ templates to implement optimizations without having to duplicate code. such as the above, where once we use CALL_2ARGS and once LT. This can be achieved with something like this when using templates (where the dead code elimination in the compiler remove the check for useLT and the unused branch of the if/else)

template <bool useLT>
void _PCQL_Heap_BubbleUp_C(...)
{
   ...
    while (i > 1) {
        ...
        if (useLT) {
            if (0 == LT(parent, elm))
                break;
        } else {
            if (False == CALL_2ARGS(isLess, parent, elm))
                break;
        }
        ...
}

• add an efficient _BinaryHeap_Create_C function which takes a list of objects and adds them all into the heap, which runs in O(n) instead of the native "insert elements using _BinaryHeap_Insert_C" which runs in O(n*log(n)). Pseudo-code from Wikipedia:

Build-Max-Heap[4] (A):
 heap_length[A] <- length[A]
   for i <- floor(length[A]/2) downto 1 do
    Max-Heapify(A, i)

and from GAP kernel's HEAP_SORT_PLIST:

  UInt len = LEN_LIST(list);
  UInt i;
  for (i = (len/2); i > 0 ; i--)
    BubbleDown(list, i, len);

[markuspf]

I used the prefix DS