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:
CPH STL Report 2015-1
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
- 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.