Heap construction: Optimal in both worst and average cases?
From MaRDI portal
Publication:6487971
DOI10.1007/BFB0015430zbMATH Open1512.68065MaRDI QIDQ6487971FDOQ6487971
Authors: Svante Carlsson, Jingsen Chen 
Publication date: 21 March 2023
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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Average case selection
- A data structure for manipulating priority queues
- BOTTOM-UP-HEAPSORT, and new variant of HEAPSORT beating, on an average, QUICKSORT (if \(n\) is not very small)
- Heaps on Heaps
- Building heaps fast
- Average-case results on heapsort
- A variant of heapsort with almost optimal number of comparisons
- An average case analysis of Floyd's algorithm to construct heaps
- Repeated random insertion into a priority queue
- On the random construction of heaps
- Average case analysis of heap building by repeated insertion
- Title not available (Why is that?)
Cited In (11)
- Performance engineering case study
- On the random construction of heaps
- Near Optimal Heap
- Average case analysis of heap building by repeated insertion
- On the complexity of building an interval heap
- A note on the construction of the data structure ``deap
- Algorithms and Data Structures
- The bounds of min-max pair heap construction
- Elementary yet precise worst-case analysis of Floyd's heap-construction program
- A tight bound on the worst-case number of comparisons for Floyd's heap construction algorithm
- Title not available (Why is that?)
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)
