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:

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.

Derek:

Is it even possible to implement a binary heap using pointers rather than an array?

kfsone:

You could use an array to store the pointers

Hogan:

there is never a reason to do so since using an array is better in every way

Jim:

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

Sinn:

its way more space efficient in its array implementation

Vamsi:

The pointer based implementation of the binary heap is incredibly difficult when compared to the array based implementation

Anubhav:

The node should have pointers to its parent, left child, and right child

CodePartizan:

you can keep track of the height of each node

Matt:

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.