Быстрые реализации приоритетной очереди

[antilamer]

Интересно, какие есть быстрые на практике реализации приоритетной очереди, кроме классической двоичной кучи

Comments

[familom]

Слышал, что pairing heaps на практике хорошо работают.

[major_m]

+1 Хотел тоже самое написать. Они в статьях выше упоминаются.

[antilamer]

Да, но не очень понятно, как сделать, чтобы они не жрали O(N) дополнительной памяти...

[major_m]

А что если к этому еще и Dynamic Succinct Tree добавить?
http://arxiv.org/pdf/0905.0768v5.pdf

Я, правда, понятия не имею, как они себя на практике ведут, но все же...

[antilamer]

Это клевая идея в общем случае, но в данном случае у операций над этими деревьями асимптотика O(log n/log log n) и скорее всего constant factor такой, что от O(log log n) в знаменателе толку мало :-/ Но все равно надо почитать.