Best case lower bounds for heapsort

DOI10.1007/BF02238646MaRDI QIDQ1195788zbMATH OpenOpenAlexFDO

Authors S. Singh

Publication date 13 January 1993

Published in Computing (Search for Journal in Brave)

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

zbMATH Keywords

lower boundcomparisonsHeapsort

Mathematics Subject Classification ID

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

Recommendations

• On the Best Case of Heapsort
• A lower bound for the worst case of bottom-up-heapsort
• Optimal heapsort algorithm
• A variant of heapsort with almost optimal number of comparisons
• Worst-case analysis of a generalized heapsort algorithm
• Worst-case analysis of generalized heapsort algorithm revisited
• Bounds for min-max heaps
• scientific article; zbMATH DE number 4195160

Cites work

• A variant of heapsort with almost optimal number of comparisons
• An average case analysis of Floyd's algorithm to construct heaps
• An optimal algorithm for deleting the root of a heap
• Average case analysis of heap building by repeated insertion
• Average-case results on heapsort
• Building heaps fast
• Heaps on Heaps
• On the random construction of heaps

Cited in

(6)

• scientific article; zbMATH DE number 4195160 (Why is no real title available?)
• Heap construction: Optimal in both worst and average cases?
• scientific article; zbMATH DE number 176500 (Why is no real title available?)
• The Analysis of Heapsort
• A lower bound for the worst case of bottom-up-heapsort
• Homogeneous and non-homogeneous algorithms

Describes a project that uses

Uses Software

• heapsort

This page was built for publication: Best case lower bounds for heapsort

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