Did you do large-scale time tests? The function HInsert looks like it has an O(n) component due to the AppendTo.
I would recommend starting with a list of fixed length maxLength and perhaps initialized e.g. ConstantArray[0,maxLength], a currentLength counter, and a function that makes a new list of length say 1.4*prior length whenever currentLength hits the current maxLength (which of course also gets modified at that point).
[Not sure if I should show this, but there already exist spelunking tools that one could use to find it.] Here is some internal code we have used for heaps. First step is to force autoload of some integer linear programming code (because I know already there is some heap code in there).
Reduce[{x - 3 y == 7, x >= -10, y <= 20}, {x, y}, Integers];
Now find out what available functionality is related to heaps.
?? *`*Heap*
(* CalculateUnits`UnitCommonSymbols`
HeapedBushels MetricHeapedBushels
Combinatorica`
Heapify
NIntegrate`
Heap HeapElements HeapInsert HeapMerge
HeapDelete HeapEmptyQ HeapLookup HeapTopElement
System`IntegerLinearDump`
HeapAdd HeapGet *)
So we have some stuff in the context "System``IntegerLinearDump``" (apologies for the doubled back-ticks, I don't know how to format them to get proper single ones). We'll put that on the context path and then have a look at Information.
AppendTo[$ContextPath, "System`IntegerLinearDump`"];
?? HeapAdd
(* System`IntegerLinearDump`HeapAdd
Attributes[HeapAdd]={HoldFirst}
HeapAdd[h_,a_,k_]:=Block[
{hole=k+1,parent,val=a[[1]]},
parent=Floor[hole/2];
While[parent!=0&&h[[parent,1]]>val,
h[[hole]]=h[[parent]];
hole=parent;
parent=Floor[hole/2]];
h[[hole]]=a] *)
?? HeapGet
(* System`IntegerLinearDump`HeapGet
Attributes[HeapGet]={HoldFirst}
HeapGet[h_,k_]:=Block[
{ans=h[[1]],hole=1,c1=2,c2,val=h[[k,1]]},
While[c1<k,
c2=c1+1;
If[c2<k,If[h[[c1,1]]<h[[c2,1]],If[h[[c1,1]]<val,
h[[hole]]=h[[c1]];hole=c1;c1=2 hole,c1=k],
If[h[[c2,1]]<val,h[[hole]]=h[[c2]];hole=c2;c1=2 hole,c1=k]],
If[h[[c1,1]]<val,h[[hole]]=h[[c1]];hole=c1;c1=2 hole,c1=k]]];
h[[hole]]=h[[k]];ans] *)
The callers of HeapAdd are responsible for checking that the length requirement is met. When exceeded, they double the heap by using Join to a List of same size, with all zeros for elements. In typical usage this will be a packed array if elements are in the machine integer range.
