The CPH STL
  Code reviews
  Contact
>Diary
  Downloads
  Literature
  Mailing list
  Mission
  Newcomer info
  Papers
  Presentations
  Reports
  Source code
  Tools
  T-shirts

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.

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. <-
© Performance Engineering Laboratory and the CPH STL contributors, 2000 - 2015
Last modification: 10.08.2015