Building heaps fast

DOI10.1016/0196-6774(89)90033-3zbMath0681.68069OpenAlexW2069635001WikidataQ56049340 ScholiaQ56049340MaRDI QIDQ4730782

Colin J. H. McDiarmid, Bruce A. Reed

Publication date: 1989

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(89)90033-3

zbMATH Keywords

average complexityheap

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05)

Related Items

An in-place heapsort algorithm requiringnlogn+nlog*n−0.546871ncomparisons ⋮ Merging heaps in parallel ⋮ An In-Place Priority Queue with O(1) Time for Push and $$\lg n + O(1)$$ lg n + O ( 1 ) Comparisons for Pop ⋮ Recurrence relations on heaps ⋮ Optimizing binary heaps ⋮ The weak-heap data structure: variants and applications ⋮ The worst case complexity of McDiarmid and Reed's variant of BOTTOM-UP HEAPSORT is less than \(n \log n+1.1n\) ⋮ Heaps with bits ⋮ QuickHeapsort: modifications and improved analysis ⋮ Best case lower bounds for heapsort ⋮ Sorting using heap structure ⋮ BOTTOM-UP-HEAPSORT, and new variant of HEAPSORT beating, on an average, QUICKSORT (if \(n\) is not very small) ⋮ A simplified complexity analysis of mcdiarmid and reed's variant of bottom-up-heapsort ⋮ QuickXsort: a fast sorting scheme in theory and practice ⋮ Building heaps in parallel ⋮ The heap-mergesort ⋮ Weak-heap sort ⋮ QuickHeapsort, an efficient mix of classical sorting algorithms