An average case analysis of Floyd's algorithm to construct heaps

DOI10.1016/S0019-9958(84)80053-4MaRDI QIDQ3718164zbMATH OpenDBLPWikidataFDO

Authors Ernst-Erich Doberkat

Publication date 1984

Published in Information and Control (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0019-9958(84)80053-4

Mathematics Subject Classification ID

Searching and sorting (68P10)

Recommendations

• Building heaps fast
• scientific article; zbMATH DE number 1984550
• Average case analysis of heap building by repeated insertion
• A tight bound on the worst-case number of comparisons for Floyd's heap construction algorithm
• On the random construction of heaps

Cited in

(17)

• Average-case results on heapsort
• The worst case complexity of McDiarmid and Reed's variant of BOTTOM-UP HEAPSORT is less than \(n \log n+1.1n\)
• BOTTOM-UP-HEAPSORT, and new variant of HEAPSORT beating, on an average, QUICKSORT (if \(n\) is not very small)
• On the random construction of heaps
• Maximum likelihood analysis of heapsort
• Average case analysis of heap building by repeated insertion
• Recurrence relations on heaps
• scientific article; zbMATH DE number 7359768 (Why is no real title available?)
• Batcher's odd-even exchange revisited: a generating functions approach
• A stochastic interpretation of propositional dynamic logic: expressivity
• Heap construction: Optimal in both worst and average cases?
• QuickXsort: a fast sorting scheme in theory and practice
• Best case lower bounds for heapsort
• scientific article; zbMATH DE number 1984550 (Why is no real title available?)
• A tight bound on the worst-case number of comparisons for Floyd's heap construction algorithm
• QuickHeapsort, an efficient mix of classical sorting algorithms
• A survey on priority queues

This page was built for publication: An average case analysis of Floyd's algorithm to construct heaps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3718164)