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.

@report{JKV2006R,
  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},
}