Быстрые реализации приоритетной очереди
Интересно, какие есть быстрые на практике реализации приоритетной очереди, кроме классической двоичной кучи.
Особенно интересует производительность decrease-key, и, крайне желательно, малое потребление памяти.
Нашёл пару статей:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.16.6563&rep=rep1&type=pdf, ftp://ftp.cs.utexas.edu/pub/techreports/honor_theses/cs-07-34-roche.pdf - исследуют несколько видов куч на практике, и у них вроде получается, что "sequence heaps" и "4-ary heaps" быстрее, чем двоичные кучи.
Ещё нашёл http://stackoverflow.com/questions/6531543/efficient-implementation-of-binary-heaps
И про cache-oblivious кучи: http://queue.acm.org/detail.cfm?id=1814327
Ещё один обзор видов куч: http://www.cs.au.dk/~gerth/papers/ianfest13.pdf
Было бы здорово, если бы кто-нибудь поделился практическим опытом.
Особенно интересует производительность decrease-key, и, крайне желательно, малое потребление памяти.
Нашёл пару статей:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.16.6563&rep=rep1&type=pdf, ftp://ftp.cs.utexas.edu/pub/techreports/honor_theses/cs-07-34-roche.pdf - исследуют несколько видов куч на практике, и у них вроде получается, что "sequence heaps" и "4-ary heaps" быстрее, чем двоичные кучи.
Ещё нашёл http://stackoverflow.com/questions/6531543/efficient-implementation-of-binary-heaps
И про cache-oblivious кучи: http://queue.acm.org/detail.cfm?id=1814327
Ещё один обзор видов куч: http://www.cs.au.dk/~gerth/papers/ianfest13.pdf
Было бы здорово, если бы кто-нибудь поделился практическим опытом.