Average-case results on heapsort

DOI10.1007/BF01937350zbMath0631.68057OpenAlexW2003642020WikidataQ56049344 ScholiaQ56049344MaRDI QIDQ1094882

Svante Carlsson

Publication date: 1987

Published in: BIT (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01937350

zbMATH Keywords

sortingaverage-case analysispriority queuesheapsheapsort

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Related Items

Recurrence relations on heaps, A note on constructing min-max heaps, 3 is more promising algorithmic parameter than 2, 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), Worst-case analysis of generalized heapsort algorithm revisited, An optimal algorithm for deleting the root of a heap, Weak-heap sort, Enumerating solutions to 𝑝(𝑎)+𝑞(𝑏)=𝑟(𝑐)+𝑠(𝑑)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A variant of heapsort with almost optimal number of comparisons
• An average case analysis of Floyd's algorithm to construct heaps