Heap construction: Optimal in both worst and average cases?

DOI10.1007/BFB0015430zbMath1512.68065MaRDI QIDQ6487971

Jingsen Chen, Svante Carlsson

Publication date: 21 March 2023

Mathematics Subject Classification ID

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

Cites Work

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

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