A variant of heapsort with almost optimal number of comparisons
From MaRDI portal
Publication:1108015
DOI10.1016/0020-0190(87)90142-6zbMath0653.68051OpenAlexW2017585246WikidataQ56049339 ScholiaQ56049339MaRDI QIDQ1108015
Publication date: 1987
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(87)90142-6
Related Items (13)
An in-place heapsort algorithm requiringnlogn+nlog*n−0.546871ncomparisons ⋮ Average-case results on heapsort ⋮ 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 worst case complexity of McDiarmid and Reed's variant of BOTTOM-UP HEAPSORT is less than \(n \log n+1.1n\) ⋮ Heaps with bits ⋮ 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 ⋮ An optimal algorithm for deleting the root of a heap ⋮ QuickHeapsort, an efficient mix of classical sorting algorithms
Cites Work
This page was built for publication: A variant of heapsort with almost optimal number of comparisons
