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

Oct 20, 2013 10:26

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

Leave a comment

sassa_nf October 20 2013, 19:00:53 UTC
конечно, быстрее всего будут очереди, где сортировка выполняется не сразу.

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

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

Reply

thedeemon October 21 2013, 06:08:06 UTC
Они ж не сортируют, лишь "слегка" упорядочивают.

Reply

sassa_nf October 21 2013, 07:13:32 UTC
хм, но ведь на вставку каждого уходит log(N) сравнений, и на удаление тоже.

Reply

thedeemon October 21 2013, 08:33:16 UTC
Что весьма неплохо для массива, который в случае поддержания отсортированности требовал бы O(N).

Reply

sassa_nf October 21 2013, 09:15:26 UTC
Ну у нас не массив, да, есть уровень indirection.

Кстати, заодно вопрос: у них что, пей-лоад просто число в этом массиве? Или расчёт на то, что выгоднее ключи в одном массиве, ссылки на пейлоад во втором массиве?

Reply

thedeemon October 21 2013, 09:19:09 UTC
У кого - "у них"? Я про бинарные кучи говорил. Что именно там хранить в ячейках - решают в зависимости от задачи.

Reply

sassa_nf October 21 2013, 09:36:05 UTC
вот, бинарные кучи. Чтобы имело смысл хранить в массиве, нужно, чтобы значения были маленькие (кэш, быстрое копирование). Если не заморачиваться хранением в массиве, то вёдра и связные списки лучше.

Например, 64-битный приоритет - значит, 8*256=2048 вёдер. Добавляем за O(1). Значения с самым высоким приоритетом (256 уровней) изымаются за O(1). Значения со следующим приоритетом (65536-256) сначала сортируются (за O(1) выбираем ведро с наименьшими 256 уровней, сортируем на 256 уровней). И т.п. Тогда высокоприоритетные элементы изымаются быстрее, низкоприоритетные изымаются медленнее, и log(N) получается лишь worst case.

Reply


Leave a comment

Up