Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
In-place Heap Construction with Optimized Comparisons, Moves, and Cache Misses
verfasst von : Jingsen Chen, Stefan Edelkamp, Amr Elmasry, Jyrki Katajainen
Erschienen in: Mathematical Foundations of Computer Science 2012
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We show how to build a binary heap in-place in linear time by performing ~ 1.625
n
element comparisons, at most ~ 2.125
n
element moves, and ~
n
/
B
cache misses, where
n
is the size of the input array,
B
the capacity of the cache line, and ~
f
(
n
) approaches
f
(
n
) as
n
grows. The same bound for element comparisons was derived and conjectured to be optimal by Gonnet and Munro; however, their procedure requires Θ(
n
) pointers and does not have optimal cache behaviour. Our main idea is to mimic the Gonnet-Munro algorithm by converting a navigation pile into a binary heap. To construct a binary heap in-place, we use this algorithm to build bottom heaps of size
$\Theta(\lg n)$
and adjust the heap order at the upper levels using Floyd’s
sift-down
procedure. On another frontier, we compare different heap-construction alternatives in practice.