16th May
2010
written by admin

I’ve seen a lot of implementations of array based binary heaps, and really only talk about tree based implementations.  Granted the array based versions that use dynamic arrays are probably better for most things since the average cost of insertion is of constant time O(1), and sorting the array based versions is much easier.  With that said I wanted to attempt a tree based version for some comparisons.  One thing to note is this a max based binary heap meaning the largest value will always be at the root.  I got some suggestions for speeding up my insertions, which turned out to be highly needed.  I’m sure theres a few ways I can improve the insertion algorithm which runs at O(log(n)) instead of the O(1) that the array based insertions take.  I’ve tested this class with over 10 million inserts and removals of varying types, and it gets the job done, but I do see that the array based implementations are superior.

Check out the code here