Design and implementation of an efficient priority queue
From MaRDI portal
Publication:4137890
DOI10.1007/BF01683268zbMath0363.60104OpenAlexW2090747326WikidataQ56453081 ScholiaQ56453081MaRDI QIDQ4137890
E. Zijlstra, Peter van Emde Boas, Rob Kaas
Publication date: 1977
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01683268
Related Items
Processing an Offline Insertion-Query Sequence with Applications, Linear size binary space partitions for fat objects, Efficient time-interval augmented spatial keyword queries on road networks, Dominance in the presence of obstacles, Spaces, Trees, and Colors, An efficient direct approach for computing shortest rectilinear paths among obstacles in a two-layer interconnection model, Unnamed Item, Longest increasing subsequence under persistent comparison errors, Integer priority queues with decrease key in constant time and the single source shortest paths problem, Four results on randomized incremental constructions, Unnamed Item, Range LCP, LZ-End Parsing in Linear Time, Locally Maximal Common Factors as a Tool for Efficient Dynamic String Algorithms., Trans-dichotomous algorithms for minimum spanning trees and shortest paths, A new approach to all-pairs shortest paths on real-weighted graphs, Efficient algorithms for the temporal precedence problem, Longest increasing subsequences in sliding windows, Predecessor queries in dynamic integer sets, Longest common extensions in trees, Rotation and lighting invariant template matching, PROCESSING AN OFFLINE INSERTION-QUERY SEQUENCE WITH APPLICATIONS, Sorting and searching revisted, Neighbours on a grid, Two- and three- dimensional point location in rectangular subdivisions, Lower bounds for dynamic algorithms, Fast and compact regular expression matching, Speeding up transposition-invariant string matching, Towards optimal parallel bucket sorting, Searching among intervals and compact routing tables, Fractional cascading. I: A data structuring technique, Sorting helps for Voronoi diagrams, On the time and space complexity of computation using write-once memory or is pen really much worse than pencil?, Fingerprints in compressed strings, Searching among intervals and compact routing tables, Computing the longest common almost-increasing subsequence, Finding shortest path in the presence of barriers: an alternate approach, Efficient testing and matching of deterministic regular expressions, Shortest paths algorithms: Theory and experimental evaluation, Full-fledged real-time indexing for constant size alphabets, Longest Common Extensions in Trees, Efficient range searching for categorical and plain data, Searching of gapped repeats and subrepetitions in a word, Algorithms for interval structures with applications, The space-optimal version of a known rectangle enclosure reporting algorithm, Cross-document pattern matching, A general label search to investigate classical graph search algorithms, The nearest colored node in a tree, Dynamic fractional cascading, Visibility and intersection problems in plane geometry, Order preserving extendible hashing and bucket tries, A parallel algorithm for finding a maximum clique of a set of circular arcs of a circle, Bounded ordered dictionaries in O(log log N) time and O(n) space, Worst-case efficient single and multiple string matching on packed texts in the word-RAM model, Hidden surface removal for rectangles, Fast computation of a longest increasing subsequence and application, A divide and conquer approach and a work-optimal parallel algorithm for the LIS problem, Faster algorithms for computing longest common increasing subsequences, Using persistent data structures for adding range restrictions to searching problems, Worst Case Efficient Single and Multiple String Matching in the RAM Model, On the generalized constrained longest common subsequence problems, How the character comparison order shapes the shift function of on-line pattern matching algorithms, A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time, Compressed data structures: Dictionaries and data-aware measures, Reducing structural changes in van Emde Boas' data structure to the lower bound for the dynamic predecessor problem, Distance Oracles for Vertex-Labeled Graphs, Handling precedence constraints in scheduling problems by the sequence pair representation, Output-sensitive generation of the perspective view of isothetic parallelepipeds, STRONGER QUICKHEAPS, Substring range reporting, Four results on randomized incremental constructions, Lower bounds for predecessor searching in the cell probe model, Fully dynamic Delaunay triangulation in logarithmic expected per operation, Adaptive sampling for geometric problems over data streams, An efficient one-side height minimization algorithm for routing around a rectangle, Dynamic relative compression, dynamic partial sums, and substring concatenation, Range-restricted mergeable priority queues, Fast geometric approximation techniques and geometric embedding problems, The complexity of coloring games on perfect graphs, Towards optimal range medians, Sequential and parallel algorithms for the maximum-weight independent set problem on permutation graphs, On sorting, heaps, and minimum spanning trees, Cache-oblivious index for approximate string matching, Output-sensitive generation of the perspective view of isothetic parallelepipeds, Unnamed Item, An algorithm for solving the longest increasing circular subsequence problem, A note on predecessor searching in the pointer machine model, Preserving order in a forest in less than logarithmic time and linear space, Extensions of self-improving sorters, Dynamic interpolation search revisited, Utilization-based admission control for aperiodic tasks under EDF scheduling, Orthogonal range searching in linear and almost-linear space, Hashed Patricia Trie: Efficient Longest Prefix Matching in Peer-to-Peer Systems, Unnamed Item, A LINEAR SPACE DATA STRUCTURE FOR ORTHOGONAL RANGE REPORTING AND EMPTINESS QUERIES, Connectivity Oracles for Graphs Subject to Vertex Failures, Parallel processing can be harmful: The unusual behavior of interpolation search, Finger search in grammar-compressed strings, Range minimum queries in minimal space, Log-logarithmic worst-case range queries are possible in space theta(N), Union and split operations on dynamic trapezoidal maps, A Survey on Priority Queues, Upper bounds for sorting integers on random access machines, An O(m log log D) algorithm for shortest paths, A priority queue in which initialization and queue operations takeO(loglogD) time, New trie data structures which support very fast search operations, Improved fast integer sorting in linear space, Computing maximum non-crossing matching in convex bipartite graphs, An efficient algorithm for enumeration of triangulations, Surpassing the information theoretic bound with fusion trees, Data structures on event graphs, A new algorithm for rectangle enclosure reporting, Optimal bounds for the predecessor problem and related problems, An axiomatic approach to time-dependent shortest path oracles
Cites Work
