A survey on priority queues
From MaRDI portal
Publication:2848973
DOI10.1007/978-3-642-40273-9_11zbMATH Open1394.68091OpenAlexW2169316699MaRDI QIDQ2848973FDOQ2848973
Authors: Gerth Stølting Brodal 
Publication date: 13 September 2013
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://pure.au.dk/ws/files/72054050/C313.pdf
Recommendations
Cites Work
- Preserving order in a forest in less than logarithmic time and linear space
- The buffer tree: A technique for designing batched external data structures
- Cache-Oblivious Algorithms
- Efficient Algorithms for Shortest Paths in Sparse Networks
- Self-adjusting binary search trees
- Log-logarithmic worst-case range queries are possible in space theta(N)
- Title not available (Why is that?)
- A tight lower bound for top-down skew heaps
- Self-Adjusting Heaps
- The derivation of a tighter bound for top-down skew heaps
- Surpassing the information theoretic bound with fusion trees
- Deterministic sorting in O ( n log log n ) time and linear space
- Design and implementation of an efficient priority queue
- A minimum spanning tree algorithm with inverse-Ackermann type complexity
- Selection and sorting with limited storage
- An optimal minimum spanning tree algorithm
- Upper bounds for time-space trade-offs in sorting and selection
- Title not available (Why is that?)
- An implicit data structure supporting insertion, deletion, and search in \(O(\log ^ 2\,n)\) time
- Weak-heap sort
- The weak-heap data structure: variants and applications
- Title not available (Why is that?)
- Black box for constant-time insertion in priority queues (note)
- Weak heaps engineered
- A data structure for manipulating priority queues
- Implementing HEAPSORT with ( n log n - 0.9 n ) and QUICKSORT with ( n log n + 0.2 n ) comparisons
- Integer priority queues with decrease key in constant time and the single source shortest paths problem
- Queaps
- An optimal algorithm for selection in a min-heap
- Implicit dictionaries with O(1) modifications per update and fast search
- Optimal worst-case operations for implicit cache-oblivious search trees.
- Power balance and apportionment algorithms for the United States Congress
- The pairing heap: A new form of self-adjusting heap
- Equivalence between priority queues and sorting
- The soft heap
- Heaps on Heaps
- Buckets, Heaps, Lists, and Monotone Priority Queues
- Fast priority queues for cached memory
- Implicit data structures for fast search and update
- An Optimal Cache‐Oblivious Priority Queue and Its Application to Graph Algorithms
- Title not available (Why is that?)
- Title not available (Why is that?)
- Implicit Data Structures for the Dictionary Problem
- A general Sequential Time-Space Tradeoff for Finding Unique Elements
- Implicit \(B\)-trees: A new data structure for the dictionary problem
- Priority queues: Small, monotone and trans-dichotomous
- Irredundant intervals
- Algorithm Theory - SWAT 2004
- Min-max heaps and generalized priority queues
- Deleting the root of a heap
- Rank-pairing heaps
- Implementation and Analysis of Binomial Queue Algorithms
- A generalization of binomial queues
- An average case analysis of Floyd's algorithm to construct heaps
- Diamond deque: A simple data structure for priority deques
- Optimal purely functional priority queues
- Two-tier relaxed heaps
- Title not available (Why is that?)
- Priority queues and sorting for read-only data
- Priority queues with update and finding minimum spanning trees
- An algorithm for merging heaps
- Symmetric min-max heap: a simpler data structure for double-ended priority queue
- Tight(er) worst-case bounds on dynamic searching and priority queues
- On RAM Priority Queues
- MERGEABLE DOUBLE-ENDED PRIORITY QUEUES
- Strict Fibonacci heaps
- The relaxed min-max heap: A mergeable double-ended priority queue
- Interval Heaps
- Correspondence-based data structures for double-ended priority queues
- Two new methods for constructing double-ended priority queues from priority queues
- On the complexity of building an interval heap
- A note on the construction of the data structure ``deap
- A Tournament Problem
- On the efficiency of pairing heaps and related data structures
- Meldable heaps and boolean union-find
- Heaps and heapsort on secondary storage
- Repeated random insertion into a priority queue
- Title not available (Why is that?)
- A Catalogue of Algorithms for Building Weak Heaps
- Melding priority queues
- Title not available (Why is that?)
- A priority queue with the time-finger property
- Worst-case optimal priority queues via extended regular counters
- A PRIORITY QUEUE WITH THE WORKING-SET PROPERTY
- Quake heaps: a simple alternative to Fibonacci heaps
- Fishspear: a priority queue algorithm
- The violation heap: a relaxed Fibonacci-like heap
- Pairing heaps with costless meld
- Parameterized self-adjusting heaps
- Thin heaps, thick heaps
- Algorithm Theory - SWAT 2004
Cited In (15)
- Strictly Implicit Priority Queues: On the Number of Moves and Worst-Case Time
- A Geo/Geo/1 inventory priority queue with self induced interruption
- A Back-to-Basics Empirical Study of Priority Queues
- Title not available (Why is that?)
- Queaps
- A fast algorithm for quadratic resource allocation problems with nested constraints
- Distribution-sensitive binomial queues.
- Priority queues and multisets
- Priority queueing involving orientation and the problems of their software implementation
- Priority queues with decreasing keys
- Revisiting priority queues for image analysis
- Smooth Heaps and a Dual View of Self-Adjusting Data Structures
- Efficiency of combining various priority queueing disciplines in computer systems
- Title not available (Why is that?)
- Algorithms and Data Structures
Uses Software
This page was built for publication: A survey on priority queues
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2848973)
