Building heaps fast

DOI10.1016/0196-6774(89)90033-3MaRDI QIDQ4730782zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Colin McDiarmid, Bruce Reed

Publication date 1989

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

Full work available at URL https://doi.org/10.1016/0196-6774(89)90033-3

zbMATH Keywords

heapaverage complexity

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4014031
• Heaps on Heaps
• Building heaps in parallel
• Algorithms and Data Structures
• Algorithm Theory - SWAT 2004
• scientific article; zbMATH DE number 1555945
• Heaps with bits
• Thin heaps, thick heaps
• Solving the heap

Cited in

(39)

• The worst case complexity of McDiarmid and Reed's variant of BOTTOM-UP HEAPSORT is less than \(n \log n+1.1n\)
• Some comments on building heaps in parallel
• Performance engineering case study
• BOTTOM-UP-HEAPSORT, and new variant of HEAPSORT beating, on an average, QUICKSORT (if \(n\) is not very small)
• On the random construction of heaps
• Maximum likelihood analysis of heapsort
• Thin heaps, thick heaps
• Near Optimal   Heap
• Average case analysis of heap building by repeated insertion
• Weak-heap sort
• Recurrence relations on heaps
• Heaps with bits
• On the complexity of building an interval heap
• Comparator networks for binary heap construction
• The weak-heap data structure: variants and applications
• A simplified complexity analysis of mcdiarmid and reed's variant of bottom-up-heapsort
• A note on the construction of the data structure ``deap
• STRONGER QUICKHEAPS
• Heaps on Heaps
• Algorithms and Data Structures
• scientific article; zbMATH DE number 140493 (Why is no real title available?)
• Elementary yet precise worst-case analysis of Floyd's heap-construction program
• An in-place priority queue with O(1) time for push and n + O(1) comparisons for pop
• An in-place heapsort algorithm requiringnlogn+nlog*n−0.546871ncomparisons
• An average case analysis of Floyd's algorithm to construct heaps
• Heap construction: Optimal in both worst and average cases?
• QuickXsort: a fast sorting scheme in theory and practice
• Best case lower bounds for heapsort
• scientific article; zbMATH DE number 1984550 (Why is no real title available?)
• Optimizing binary heaps
• A tight bound on the worst-case number of comparisons for Floyd's heap construction algorithm
• Sorting using heap structure
• QuickHeapsort, an efficient mix of classical sorting algorithms
• scientific article; zbMATH DE number 4014031 (Why is no real title available?)
• scientific article; zbMATH DE number 742986 (Why is no real title available?)
• The heap-mergesort
• Building heaps in parallel
• Merging heaps in parallel
• Comparator networks for binary heap construction

This page was built for publication: Building heaps fast

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