Heap construction: Optimal in both worst and average cases?

DOI10.1007/BFB0015430MaRDI QIDQ6487971zbMATH OpenFDO

Authors Svante Carlsson, Jingsen Chen

Publication date 21 March 2023

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05)

Recommendations

• scientific article; zbMATH DE number 1984550
• Average case analysis of heap building by repeated insertion
• On the Best Case of Heapsort
• Optimal parallel construction of heaps
• An average case analysis of Floyd's algorithm to construct heaps
• Best case lower bounds for heapsort
• Optimal algorithms for inserting a random element into a random heap
• A tight bound on the worst-case number of comparisons for Floyd's heap construction algorithm
• Worst-case analysis of a generalized heapsort algorithm

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 742986 (Why is no real title available?)
• A data structure for manipulating priority queues
• A variant of heapsort with almost optimal number of comparisons
• An average case analysis of Floyd's algorithm to construct heaps
• Average case analysis of heap building by repeated insertion
• Average case selection
• Average-case results on heapsort
• BOTTOM-UP-HEAPSORT, and new variant of HEAPSORT beating, on an average, QUICKSORT (if \(n\) is not very small)
• Building heaps fast
• Heaps on Heaps
• On the random construction of heaps
• Repeated random insertion into a priority queue

Cited in

(11)

• Average case analysis of heap building by repeated insertion
• Near Optimal   Heap
• A note on the construction of the data structure ``deap
• scientific article; zbMATH DE number 742986 (Why is no real title available?)
• Algorithms and Data Structures
• A tight bound on the worst-case number of comparisons for Floyd's heap construction algorithm
• The bounds of min-max pair heap construction
• On the random construction of heaps
• Elementary yet precise worst-case analysis of Floyd's heap-construction program
• Performance engineering case study
• On the complexity of building an interval heap

This page was built for publication: Heap construction: Optimal in both worst and average cases?

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