An In-Place Priority Queue with O(1) Time for Push and $$\lg n + O(1)$$ lg n + O ( 1 ) Comparisons for Pop

DOI10.1007/978-3-319-20297-6_14zbMath1465.68058OpenAlexW2282158473MaRDI QIDQ3194717

Amr Elmasry, Jyrki Katajainen, Stefan Edelkamp

Publication date: 20 October 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-20297-6_14

Mathematics Subject Classification ID

Data structures (68P05)

Related Items

Optimizing binary heaps

Cites Work

• Weak heaps engineered
• Heaps with bits
• An optimal algorithm for deleting the root of a heap
• A variant of heapsort with almost optimal number of comparisons
• The worst case complexity of McDiarmid and Reed's variant of BOTTOM-UP HEAPSORT is less than \(n \log n+1.1n\)
• Weak-heap sort
• FAT HEAPS WITHOUT REGULAR COUNTERS
• In-place Heap Construction with Optimized Comparisons, Moves, and Cache Misses
• Heaps on Heaps
• A data structure for manipulating priority queues
• Implementation and Analysis of Binomial Queue Algorithms
• Building heaps fast
• Multipartite priority queues
• Algorithm Theory - SWAT 2004
• Unnamed Item
• Unnamed Item
• Unnamed Item