A priority queue with the time-finger property

DOI10.1016/j.jda.2012.04.014zbMath1257.68061OpenAlexW2080439633MaRDI QIDQ1932364

John Iacono, Amr Elmasry, Arash Farzan

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.014

zbMATH Keywords

data structurespriority queuessplay treesdistribution-sensitive structuresworking-set bound

Mathematics Subject Classification ID

Trees (05C05) Data structures (68P05)

Related Items

Smooth Heaps and a Dual View of Self-Adjusting Data Structures ⋮ A Survey on Priority Queues

Cites Work

• Unnamed Item
• Unnamed Item
• Sequential access in splay trees takes linear time
• The pairing heap: A new form of self-adjusting heap
• Queaps
• On the sequential access theorem and deque conjecture for splay trees
• A unified access bound on comparison-based dynamic dictionaries
• Self‐adjusting trees in practice for large text collections
• Worst-Case Optimal Priority Queues via Extended Regular Counters
• A Unifying Property for Distribution-Sensitive Priority Queues
• A PRIORITY QUEUE WITH THE WORKING-SET PROPERTY
• Meldable heaps and boolean union-find
• Self-adjusting binary search trees
• A data structure for manipulating priority queues
• On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof