Optimizing binary heaps

DOI10.1007/S00224-017-9760-2MaRDI QIDQ2411045zbMATH OpenOpenAlexFDO

Authors Stefan Edelkamp, Amr Elmasry, Jyrki Katajainen

Publication date 20 October 2017

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://kclpure.kcl.ac.uk/portal/en/publications/optimizing-binary-heaps(13ac33fa-bd7d-4059-b124-d8eaffcbb78b).html

zbMATH Keywords

binary heapscomparison complexityconstant factorsin-place data structurespriority queues

Mathematics Subject Classification ID

Data structures (68P05)

Recommendations

• An in-place priority queue with O(1) time for push and n + O(1) comparisons for pop
• Heaps on Heaps
• Cascade heap: towards time-optimal extractions
• A survey on priority queues
• Refined complexity analysis for heap operations

Cites work

• A catalogue of algorithms for building weak heaps
• A characterization of heaps and its applications
• A data structure for manipulating priority queues
• A lower bound for the worst case of bottom-up-heapsort
• A Simple Modification of Xunrang and Yuzhang'S HEAPSORT Variant Improving its Complexity Significantly
• A variant of heapsort with almost optimal number of comparisons
• Adaptive Heapsort
• An in-place priority queue with O(1) time for push and n + O(1) comparisons for pop
• An optimal algorithm for deleting the root of a heap
• Asymptotic optimal HEAPSORT algorithm
• Average case analysis of heap building by repeated insertion
• Binary Search Trees of Bounded Balance
• Black box for constant-time insertion in priority queues (note)
• BOTTOM-UP-HEAPSORT, and new variant of HEAPSORT beating, on an average, QUICKSORT (if \(n\) is not very small)
• Building heaps fast
• Deterministic sorting in O(nloglogn) time and linear space
• Elementary yet precise worst-case analysis of Floyd's heap-construction program
• Equivalence between priority queues and sorting
• Heaps on Heaps
• Heaps with bits
• scientific article; zbMATH DE number 4062572 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 1178976 (Why is no real title available?)
• scientific article; zbMATH DE number 1444318 (Why is no real title available?)
• Implementation and Analysis of Binomial Queue Algorithms
• In-place Heap Construction with Optimized Comparisons, Moves, and Cache Misses
• Introduction to algorithms.
• Memory-Adjustable Navigation Piles with Applications to Sorting and Convex Hulls
• On the Best Case of Heapsort
• Optimal heapsort algorithm
• Priority queues with update and finding minimum spanning trees
• Strictly implicit priority queues: on the number of moves and worst-case time
• The Analysis of Heapsort
• The design of dynamic data structures
• The weak-heap data structure: variants and applications
• The worst case complexity of McDiarmid and Reed's variant of BOTTOM-UP HEAPSORT is less than \(n \log n+1.1n\)
• Two new methods for constructing double-ended priority queues from priority queues
• Two skew-binary numeral systems and one application
• Weak heaps engineered
• Weak-heap sort

Cited in

(11)

• A survey on priority queues
• In-place Heap Construction with Optimized Comparisons, Moves, and Cache Misses
• An in-place priority queue with O(1) time for push and n + O(1) comparisons for pop
• Strictly implicit priority queues: on the number of moves and worst-case time
• Heaps on Heaps
• Weak heaps engineered
• Explaining binomial heaps
• Refined complexity analysis for heap operations
• Cascade heap: towards time-optimal extractions
• Cascade heap: towards time-optimal extractions
• Linear-algebraic implementation of Fibonacci heap

Describes a project that uses

Uses Software

• heapsort

This page was built for publication: Optimizing binary heaps

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