Performance engineering case study: Heap construction
Authors:Jesper Bojesen, Jyrki Katajainen, and Maz Spork
Publication:Report 99/12, Department of Computer Science, University of Copenhagen (1999), 44 app.pp.
Full text:<ps.gif>PS (754 kB)  
Abstract:The behaviour of three methods for constructing a binary heap is studied. The methods considered are the original one proposed by Williams [1964], in which elements are repeatedly inserted into a single heap; the improvement by Floyd [1964], in which small heaps are repeatedly merged to bigger heaps; and a recent method proposed, e. g., by Fadel et al. [1999] in which a heap is built layerwise. Both the worst-case number of instructions and that of cache misses are analysed. It is well-known that Floyd’s method has the best instruction count. Let N denote the size of the heap to be constructed, B the number of elements that fit into a cache line, and let c and d be some positive constants. Our analysis shows that, under reasonable assumptions, repeated insertion and layerwise construction both incur at most c N/B cache misses, whereas repeated merging, as programmed by Floyd, can incur more than (d N log2 B)/B cache misses. However, for our memory-tuned versions of repeated insertion and repeated merging the number of cache misses incurred is close to the optimal bound N/B.
Related:<html.gif>HTML (Conference version)  <html.gif>HTML (Journal version)  
  author = {Jesper Bojesen and Jyrki Katajainen and Maz Spork},
  title = {Performance engineering case study: {H}eap construction},
  type = {Report},
  number = {99/12},
  institution = {Department of Computer Science, University of Copenhagen},
  year = {1999},
  pagetotal = {44},
This page was generated by Jyrki Katajainen <> on 28.12.2011.