The Analysis of Heapsort

DOI10.1006/JAGM.1993.1031MaRDI QIDQ3141523zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Russel Schaffer, Robert Sedgewick

Publication date 6 December 1993

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

Full work available at URL https://semanticscholar.org/paper/2f918427b41bef546b8225f5fb32c0b1edd67860

zbMATH Keywords

expected complexityheapsortimplicit data structuressorting

Mathematics Subject Classification ID

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

Recommendations

• On the Best Case of Heapsort
• A variant of heapsort with almost optimal number of comparisons
• Sorting using heap structure
• Best case lower bounds for heapsort
• scientific article; zbMATH DE number 1629853

Cited in

(17)

• \(\mathcal{MOQA}\); unlocking the potential of compositional static average-case analysis
• 3 is more promising algorithmic parameter than 2
• The heap-mergesort
• Almost-sure asymptotics for the number of heaps inside a random sequence
• Recurrence relations on heaps
• Entropy conservation for comparison-based algorithms
• Optimizing binary heaps
• A Simple Modification of Xunrang and Yuzhang'S HEAPSORT Variant Improving its Complexity Significantly
• scientific article; zbMATH DE number 1543353 (Why is no real title available?)
• A tight bound on the worst-case number of comparisons for Floyd's heap construction algorithm
• Homogeneous and non-homogeneous algorithms
• Fractal analysis of pi normality
• Average-case analysis via incompressibility
• Maximum likelihood analysis of heapsort
• Tables
• Heaps with bits
• Multiway in-place merging

This page was built for publication: The Analysis of Heapsort

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