Experimental evaluation of local heaps
Authors:Claus Jensen, Jyrki Katajainen, and Fabio Vitale
Publication:CPH STL Report 2006-1, Department of Computer Science, University of Copenhagen (2006), 25 pp.
Full text:<pdf.gif>PDF (247 kB)  <ps.gif>PS (708 kB)  

In this paper we present a cache-aware realization of a priority queue, named a local heap, which is a slight modification of a standard binary heap. The new data structure is cache efficient, has a small computational overhead, and achieves a good worst-case performance with respect to the number of element comparisons and the number of element moves. We show both theoretically and experimentally that the data structure is competitive with a standard binary heap, provided that the number of elements stored is not small.

Related:<html.gif>HTML (Compressed tar ball)  <html.gif>HTML (Slides)  
  author = {Claus Jensen and Jyrki Katajainen and Fabio Vitale},
  title = {Experimental evaluation of local heaps},
  type = {CPH STL Report},
  number = {2006-1},
  institution = {Department of Computer Science, University of Copenhagen},
  year = {2006},
  pagetotal = {25},
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 15.11.2012.