Очередь с минимальным приоритетом с постоянной кнопкой увеличения времени

Question

Я некоторое время искал вариант реализации с минимальной кучей, который вместо амортизированного O (1) для уменьшения ключа предлагает O (1) для его увеличения. (С обменом на наличие операции нажатия клавиши со стоимостью o (log (n)), поскольку при здесь наблюдается, что обе вещи невозможны одновременно).

У меня фактически есть набор элементов фиксированного размера, и я хочу выполнить приращение по клавишам или заменить минимальный элемент большим. Так что другой подход, который удовлетворяет этому, также был бы великолепен!

Кто-нибудь знает вариацию кучи с постоянным амортизированным временем нажатия клавиши увеличения времени?

Спасибо!

Answer 1

На самом деле ссылка, на которую вы указываете, говорит о том, что три операции, которые вы не можете выполнять вместе, это O(1) для insert, find-min и increase-key. Операция decrease-key не входит в это. Так что одну из других операций придется увеличить. Я сомневаюсь, что это возможно.

Но, тем не менее, куча Фибоначчи действительно предлагает амортизированное случайное O(1) увеличение ключа. То есть для половины элементов вам не нужно его перемещать. За четверть вы должны переместить его один раз. Для 1/8 вы должны переместить его дважды, и так далее. Наихудший случай O(log(n)) оплачивается только при увеличении нижнего элемента. Таким образом, средняя стоимость увеличения случайного элемента составляет O(1).

Вы даже можете сделать кучу лучше, чем это. Когда вы увеличиваете значение элемента, вы можете пометить его как увеличенное и сделать ленивым его на самом деле. Пока он не достигнет дна, вам не нужно его вообще двигать. Поэтому, в зависимости от использования, большую часть времени вам вообще не нужно платить за перемещение вещей.

Answer 2

Я думаю, что вы оптимизируете слишком рано. Я рекомендую, чтобы вы запустили ваше приложение с кучей сопряжения, а затем профилировали его. Слишком много вещей, которые вы еще не знаете о данных и о том, как будет работать структура кучи.

Биноминальная куча, куча Фибоначчи, сопряженная куча и многие другие варианты довольно сложно проанализировать, поскольку их поведение во многом зависит от сочетания операций, порядка операций и характера данных. Например, в куче сопряжения клавиша увеличения равна O (1), если у узла нет дочерних элементов. И то, имеет ли узел дочерние элементы, зависит от того, где находится узел в куче и сколько раз были вызваны клавиша уменьшения или remove-first .

Я сомневаюсь, что вы найдете структуру кучи с удалением O (1) и логарифмической вставкой. Четная очередь Бродала , которая имеет O (1) для всего остального, является O (log n) для удаления. Отметим, однако, что хотя очередь Бродала асимптотически оптимальна, она, по словам самого Бродала, «довольно сложна» и «[не] практична на практике».

Запустите вашу программу. Профиль это. Затем решите, нужна ли вам более производительная структура очереди с приоритетами.