Приоритетная очередь — двоичная куча

Я пытаюсь реализовать приоритетную очередь как минимальную двоичную кучу с отсортированным массивом. Я пытаюсь заставить функцию update_key работать за логарифмическое время, но для этого мне нужно знать позицию элемента в массиве. Можно ли как-то это сделать без использования карты? Если да, то как? Спасибо


c++ arrays map priority-queue binary-heap
person Richard    schedule 15.04.2012    source источник
comment
Что такое функция update_key?   -  person DRVic    schedule 15.04.2012
comment
функция, которая обновляет ключ элемента, поскольку двоичная куча содержит пару ключей и элементов   -  person Richard    schedule 15.04.2012

Ответы (3)


arrow_upward
2
arrow_downward

Если вы действительно хотите иметь возможность изменить ключ произвольного элемента, куча — не лучший выбор структуры данных. Что это дает вам, так это сочетание:

  1. компактное представление (без указателей, только массив и неявная схема индексации)
  2. логарифмическая вставка, перебалансировка
  3. логарифмическое удаление наименьшего (наибольшего) элемента.
  4. O(1) доступ к значению наименьшего (наибольшего) элемента. -

Дополнительным преимуществом 1. является то, что отсутствие указателей означает, что вы делаете значительно меньше вызовов malloc/free (new/delete). Карта (представленная в стандартной библиотеке в виде сбалансированного двоичного дерева) дает вам два средних из них, добавляя в

  1. логарифмический find() по любому ключу.

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

person DRVic    schedule 16.04.2012

arrow_upward
0
arrow_downward

Ваша функция поиска ключа должна работать за логарифмическое время. Ваше обновление (смена ключа) должно происходить постоянно. Ваша функция удаления должна выполняться за время log(n). Ваша функция вставки должна быть log(n) раз.

Если эти предположения верны, попробуйте следующее: 1) Найдите свой элемент в своей куче (IE: двоичный поиск, поскольку это отсортированный массив). 2) Обновите свой ключ (вы просто меняете значение, постоянное время). 3) Удалите элемент из журнала кучи (n) для повторной кучи.
4) Вставьте свой элемент в журнал кучи (n).

Итак, у вас будет log(n) + 1 + log(n) + log(n), что сводится к log(n).

Примечание: это амортизируется, потому что, если вам нужно перераспределить свой массив и т. Д., Это добавляет накладные расходы. Но в любом случае не стоит делать это слишком часто.

person David D    schedule 15.04.2012
comment
Я не думаю, что он имеет в виду отсортированный массив. Типичная реализация двоичной кучи хранит элементы в массиве, но только свойство кучи должно быть истинным. Думаю, невозможно сохранить все элементы отсортированными и по-прежнему иметь сложность O (log (n)) для вставки и удаления элемента. - person Ivaylo Strandjev; 15.04.2012
comment
В этом есть смысл. Предполагая, что используется реальная структура кучи, корневой узел кучи просто должен быть лучше (с точки зрения сортировки), чем два дочерних элемента, тогда каждый дочерний элемент может считаться корнем другой кучи, и это применяется рекурсивно). Я не знаю, почему это не пришло мне в голову прошлой ночью. Спасибо за разъяснения. - person David D; 15.04.2012

arrow_upward
0
arrow_downward

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

Одним из решений было бы это. Куча содержит объекты типа C*. C — это класс с int членом heap_index, который является индексом объекта в массиве кучи. Всякий раз, когда вы перемещаете элемент внутри массива кучи, вам придется обновить его heap_index, чтобы установить для него новый индекс.

Update_key (а также удаление произвольного элемента) в этом случае занимает время log(n), потому что требуется постоянное время, чтобы найти элемент (через heap_index), и log(n) время, чтобы переместить его в правильную позицию.

person DS.    schedule 15.04.2012