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

[antilamer]

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

Comments

[familom]

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

[major_m]

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

[antilamer]

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

[major_m]

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

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

[sassa_nf]

конечно, быстрее всего будут очереди, где сортировка выполняется не сразу.

Например, если у нас в среднем поровну выполняется insert и delete_min, то выгодно хранить сортированными только n элементов, а остальные расставить по вёдрам частично отсортированными. Тогда хотя и логарифмическое время, но логарифм будет от числа n - среднее количество элементов в последнем ведре - меньше N - полное содержимое очереди.

Все эти binary heaps и друзья всегда сортируют все элементы.

[thedeemon]

Они ж не сортируют, лишь "слегка" упорядочивают.

[sassa_nf]

хм, но ведь на вставку каждого уходит log(N) сравнений, и на удаление тоже.

[thedeemon]

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