конечно, быстрее всего будут очереди, где сортировка выполняется не сразу.
Например, если у нас в среднем поровну выполняется insert и delete_min, то выгодно хранить сортированными только n элементов, а остальные расставить по вёдрам частично отсортированными. Тогда хотя и логарифмическое время, но логарифм будет от числа n - среднее количество элементов в последнем ведре - меньше N - полное содержимое очереди.
Все эти binary heaps и друзья всегда сортируют все элементы.
Кстати, заодно вопрос: у них что, пей-лоад просто число в этом массиве? Или расчёт на то, что выгоднее ключи в одном массиве, ссылки на пейлоад во втором массиве?
вот, бинарные кучи. Чтобы имело смысл хранить в массиве, нужно, чтобы значения были маленькие (кэш, быстрое копирование). Если не заморачиваться хранением в массиве, то вёдра и связные списки лучше.
Например, 64-битный приоритет - значит, 8*256=2048 вёдер. Добавляем за O(1). Значения с самым высоким приоритетом (256 уровней) изымаются за O(1). Значения со следующим приоритетом (65536-256) сначала сортируются (за O(1) выбираем ведро с наименьшими 256 уровней, сортируем на 256 уровней). И т.п. Тогда высокоприоритетные элементы изымаются быстрее, низкоприоритетные изымаются медленнее, и log(N) получается лишь worst case.
Например, если у нас в среднем поровну выполняется insert и delete_min, то выгодно хранить сортированными только n элементов, а остальные расставить по вёдрам частично отсортированными. Тогда хотя и логарифмическое время, но логарифм будет от числа n - среднее количество элементов в последнем ведре - меньше N - полное содержимое очереди.
Все эти binary heaps и друзья всегда сортируют все элементы.
Reply
Reply
Reply
Reply
Кстати, заодно вопрос: у них что, пей-лоад просто число в этом массиве? Или расчёт на то, что выгоднее ключи в одном массиве, ссылки на пейлоад во втором массиве?
Reply
Reply
Например, 64-битный приоритет - значит, 8*256=2048 вёдер. Добавляем за O(1). Значения с самым высоким приоритетом (256 уровней) изымаются за O(1). Значения со следующим приоритетом (65536-256) сначала сортируются (за O(1) выбираем ведро с наименьшими 256 уровней, сортируем на 256 уровней). И т.п. Тогда высокоприоритетные элементы изымаются быстрее, низкоприоритетные изымаются медленнее, и log(N) получается лишь worst case.
Reply
Leave a comment