The weak-heap data structure: variants and applications

DOI10.1016/j.jda.2012.04.010zbMath1257.68059OpenAlexW1968564979MaRDI QIDQ1932363

Jyrki Katajainen, Amr Elmasry, Stefan Edelkamp

Publication date: 18 January 2013

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

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

zbMATH Keywords

data structuresshortest pathsadaptive sortingpriority queuesweak heapscomparison complexity

Mathematics Subject Classification ID

Searching and sorting (68P10) Data structures (68P05)

Related Items

Regular numeral systems for data structures ⋮ Optimizing binary heaps ⋮ Weak heaps engineered ⋮ Bipartite binomial heaps ⋮ A Survey on Priority Queues

Uses Software

• LEDA
• Quicksort
• heapsort

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Two-tier relaxed heaps
• The pairing heap: A new form of self-adjusting heap
• Splitsort -- an adaptive sorting algorithm
• Weak-heap sort
• Shortest paths algorithms: Theory and experimental evaluation
• A theorem on the expected complexity of dijkstra's shortest path algorithm
• A unifying look at data structures
• A data structure for manipulating priority queues
• Implementation and Analysis of Binomial Queue Algorithms
• Adaptive Heapsort
• Building heaps fast
• Multipartite priority queues
• Fibonacci heaps and their uses in improved network optimization algorithms
• On the adaptiveness of Quicksort
• Inversion-sensitive sorting algorithms in practice
• Implementing HEAPSORT with ( n log n - 0.9 n ) and QUICKSORT with ( n log n + 0.2 n ) comparisons
• Automata, Languages and Programming
• Rank-Pairing Heaps
• Quicksort