Searching and Priority Queues in o(log n) Time*
Arne Andersson
Uppsala University
40.4Achieving Sub-Logarithmic Time per Element by Simple Means.
Range Reduction•Packing Keys• Combining
40.5Deterministic Algorithms and Linear Space.
Fusion Trees•Exponential Search Trees
40.6From Amortized Update Cost to Worst-Case
40.7Sorting and Priority Queues
Range Reduction•Packed Sorting•Combining the Techniques•Further Techniques and Faster Randomized Algorithms
In many cases of algorithm design, the comparison-based model of computation is not the obvious choice. In this chapter, we show how to design data structures with very good complexity on a realistic model of ...
Get Handbook of Data Structures and Applications, 2nd Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.