In-place heap construction with optimized comparisons, moves, and cache misses

TY - GEN

T1 - In-place heap construction with optimized comparisons, moves, and cache misses

AU - Chen, Jingsen

AU - Edelkamp, Stefan

AU - Elmasry, Amr Ahmed Abd Elmoneim

AU - Katajainen, Jyrki

N1 - Conference code: 37

PY - 2012

Y1 - 2012

N2 - We show how to build a binary heap in-place in linear time by performing ~ 1.625n element comparisons, at most ~ 2.125n 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 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.

AB - We show how to build a binary heap in-place in linear time by performing ~ 1.625n element comparisons, at most ~ 2.125n 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 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.

U2 - 10.1007/978-3-642-32589-2_25

DO - 10.1007/978-3-642-32589-2_25

M3 - Article in proceedings

SN - 978-3-642-32588-5

T3 - Lecture notes in computer science

SP - 259

EP - 270

BT - Mathematical Foundations of Computer Science 2012

A2 - Rovan, Branislav

A2 - Sassone, Vladimiro

A2 - Widmayer, Peter

PB - Springer

T2 - 37th International Symposium on Mathematical Foundations of Computer Science

Y2 - 27 August 2012 through 31 August 2012

ER -