Использование позиции в очереди с возможностью адаптации

Question

Какой смысл использовать Позицию в очереди с адаптивными приоритетами (список на основе кучи для ключей), когда нам все равно нужно передать ссылку Entry на функции remove (k), replaceKey (k). Т.е. если у меня есть какая-то ссылка «ref» на запись в очереди, тогда я могу просто вызвать remove (ref) и replaceKey (ref), и это все равно займет O (1) время. Зачем мне нужна специальная должность для этого?

Answer 1

1. Нет смысла реализовывать кучу как связанный список. Кучи по своей природе являются неполными двоичными деревьями. Вы можете хранить кучу в массиве, потому что легко вычислить индекс массива дочерних узлов: дочерние элементы узла в позиции i живут в позициях 2i + 1 и 2i + 2. Гораздо эффективнее найти i-й элемент массива, чем i-й элемент связанного списка.

2. Для адаптируемых очередей приоритетов Массив (куча) представляет собой последовательность ссылок на экземпляры позиций, каждый из которых хранит ключ, значение и текущий индекс элемента в массиве. Пользователю будет предоставлена ​​ссылка на экземпляр Position для каждого вставленного элемента. Когда мы выполняем приоритетные операции с очередями в нашей куче, и элементы перемещаются в нашей структуре мы перемещаем экземпляры позиции в массиве и обновите третье поле каждой позиции, чтобы отразить его новый индекс в массиве, и обновление займет O (log (n)) сложность времени.