All-in-one implementation framework for binary heaps: Electronic appendix
Author:Jyrki Katajainen
Publication:CPH STL Report 2015-2, Department of Computer Science, University of Copenhagen (2015), 111 pp.
Full text:<pdf.gif>PDF (524 kB)  
Abstract:In the paper "All-in-one implementation framework for binary heaps", I described a generic framework for implementing a binary heap. By customizing the type parameters, I used the framework to derive 14 different implementations. Then I benchmarked these implementations against each other and against some of the best competitors. My conclusion is that the paper describes the state of the art: After optimizing the code, the framework had very little overhead which was a central question raised in the paper. In this electronic appendix, and in an accompanying tar ball, I release the source code described, discussed, and benchmarked.

My motivation for writing the paper came from some discussions I found on the Internet when googling with the words "pointer-based binary heap". By reading the top-10 answers, it was easy to identify a set of implementation alternatives and potential problems with them:

implicit structure:
An array of values; easy to implement and space efficient; can have a catch in dynamization
referent structure:
An array of pointers to values; still easy to get access to the neighbours of a node
linked structure:
A binary tree of nodes, each storing a value and pointers to nodes; challenging to get correct; how to keep track of the last leaf; how many pointers to use; should there be other information at the nodes.

In addition, several metrics how the efficiency should be measured were specified: worst-case running time, average-case running time, amortized running time, and space consumption. However, very few facts were given how well different alternatives perform according to these metrics. By reading the paper and running the code, you can determine what is the best alternative for your application.

Related:<html.gif>HTML (Journal article)  <html.gif>HTML (Technical report)  <html.gif>HTML (tar ball)  
BibLATEX:
@report{Kat2015S,
  author = {Jyrki Katajainen},
  title = {All-in-one implementation framework for binary heaps: Electronic
    appendix},
  type = {CPH STL Report},
  number = {2015-2},
  institution = {Department of Computer Science, University of Copenhagen},
  year = {2015},
  pagetotal = {111},
}
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 17.05.2017.