Weak heaps engineered

DOI10.1016/j.jda.2013.07.002zbMath1334.68051OpenAlexW1966892175MaRDI QIDQ396692

Jyrki Katajainen, Amr Elmasry, Stefan Edelkamp

Publication date: 13 August 2014

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

Full work available at URL: https://doi.org/10.1016/j.jda.2013.07.002

zbMATH Keywords

data structurespriority queuesconstant factorsweak heaps

Mathematics Subject Classification ID

Data structures (68P05)

Related Items (5)

Strictly Implicit Priority Queues: On the Number of Moves and Worst-Case Time ⋮ An In-Place Priority Queue with O(1) Time for Push and $$\lg n + O(1)$$ lg n + O ( 1 ) Comparisons for Pop ⋮ Optimizing binary heaps ⋮ Priority Queues and Sorting for Read-Only Data ⋮ A Survey on Priority Queues

Uses Software

• heapsort

Cites Work

• Unnamed Item
• Unnamed Item
• BOTTOM-UP-HEAPSORT, and new variant of HEAPSORT beating, on an average, QUICKSORT (if \(n\) is not very small)
• Weak-heap sort
• The weak-heap data structure: variants and applications
• In-place Heap Construction with Optimized Comparisons, Moves, and Cache Misses
• Black box for constant-time insertion in priority queues (note)
• A data structure for manipulating priority queues
• Multipartite priority queues
• Performance engineering case study
• Implementing HEAPSORT with ( n log n - 0.9 n ) and QUICKSORT with ( n log n + 0.2 n ) comparisons

This page was built for publication: Weak heaps engineered