A framework summer [August 10th, 2015]

I just finished a paper entitled "All-in-one implementation framework for binary heaps". Looking at my notes, I can see that it took two months to write this paper. So this is how I have used my summer. If you want to enjoy the fun (not the sun), you can read the paper and take a peek into the code:

Paper: CPH STL Report 2015-1
Code: CPH STL Report 2015-2

My motivation for writing this paper came from some discussions I found on the Internet when googling with the words "pointer-based binary heap". Below you get an extract of the opinions expressed on different implementations.

Is it even possible to implement a binary heap using pointers rather than an array?
You could use an array to store the pointers
there is never a reason to do so since using an array is better in every way
it’s inefficient in the extreme to implement a binary heap in a linked tree structure, especially when doing so in an array is much easier
its way more space efficient in its array implementation
The pointer based implementation of the binary heap is incredibly difficult when compared to the array based implementation
The node should have pointers to its parent, left child, and right child
you can keep track of the height of each node
Theres no easy way to do it unless its vector based

What is the best way of implementing a binary heap? Is there any reason to use pointers? What is the truth in this matter? Hopefully, this made you curious.

All rights reserved Jyrki Katajainen. <-
© Performance Engineering Laboratory and the CPH STL contributors, 2000–2018
Last modification: 2018-01-31