Worst-Case Optimal Priority Queues via Extended Regular Counters
arXiv: 1112.0993
Worst-Case Optimal Priority Queues via Extended Regular Counters
We consider the classical problem of representing a collection of priority queues under the operations \Findmin{}, \Insert{}, \Decrease{}, \Meld{}, \Delete{}, and \Deletemin{}. In the comparison-based model, if the first four operations are to be supported in constant time, the last two operations must take at least logarithmic time. Brodal showed that his worst-case efficient priority queues achieve these worst-case bounds. Unfortunately, this data structure is involved and the time bounds hide large constants. We describe a new variant of the worst-case efficient priority queues that relies on extended regular counters and provides the same asymptotic time and space bounds as the original. Due to the conceptual separation of the operations on regular counters and all other operations, our data structure is simpler and easier to describe and understand. Also, the constants in the time and space bounds are smaller. In addition, we give an implementation of our structure on a pointer machine. For our pointer-machine implementation, \Decrease{} and \Meld{} are asymptotically slower and require $O(\lg\lg{n})$ worst-case time, where $n$ denotes the number of elements stored in the resulting priority queue.
- University of Copenhagen Denmark
- University of Copenhagen Denmark
- University of Copenhagen Denmark
- University of Copenhagen (UCPH) Denmark
- University of Copenhagen Denmark
FOS: Computer and information sciences, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS)
FOS: Computer and information sciences, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS)
8 Research products, page 1 of 1
- 2012IsAmongTopNSimilarDocuments
- 2012IsAmongTopNSimilarDocuments
- 2010IsAmongTopNSimilarDocuments
- 1999IsAmongTopNSimilarDocuments
- 2010IsAmongTopNSimilarDocuments
- 2007IsAmongTopNSimilarDocuments
- 2012IsAmongTopNSimilarDocuments
- 2011IsAmongTopNSimilarDocuments
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).5 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
