New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Implement various priority queue data structures #35

Open

9 tasks

krzysztof-turowski opened this issue Jul 10, 2024 · 0 comments

Labels

algorithms documentation

Owner

krzysztof-turowski commented Jul 10, 2024 •

edited

Loading

Example alternatives to well-known priority queues:

Sleator, Tarjan (1986) - Self-adjusting heaps - skew heap
Brodal (1996) - Worst-case efficient priority queues - Brodal queue
Thorup (2000) - On RAM priority queues
Chazelle (2000) - The soft heap: An approximate priority queue with optimal error rate - soft heap
Brodal (2021) - Soft Sequence Heaps - soft heap
Haeupler, Sen, Tarjan (2011) - Rank-pairing heaps
Brodal, Lagogiannis, Tarjan (2012) - Strict Fibonacci heaps

Priority queues for integers:

van Emde Boas (1977) - Preserving order in a forest in less than logarithmic time and linear space + Design and implementation of an efficient priority queue - van Emde Boas trees
Fredman, Willard (1990) - BLASTING Through the Information Theoretic Barrier with FUSION TREES - fusion trees
See also Willard (1992) - Applications of the fusion tree method to computational geometry and searching.

krzysztof-turowski added documentation algorithms labels

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment