Как заставить ключ уменьшения в биномиальной куче работать во время логарифма

Question

Интерфейс, предоставляемый книгой "Введение в алгоритм" уменьшения ключа в биномиальной куче: BINOMIAL-HEAP-DECREASE-KEY (H,x,k), где H - указатель на первый корень дерева, x - это "индекс" узла, ключ которого должен быть уменьшен до k. И сложность времени O(logn)

Однако мы обычно используем связанный список для реализации биномиальной кучи, где нет прямого доступа к x без выполнения поиска, что в общем случае равно O(n).

Одним из способов решения этой проблемы является сохранение указателя для каждого узла в биномиальной куче, который затем обеспечивает прямой доступ к каждому узлу в O(1), но тогда сложность пространства равна O(n).

Кто-нибудь знает лучшие решения для этого? Спасибо!

Предыдущее обсуждение можно найти здесь.

Answer 1

Если мы храним кучу в массиве, мы можем легко это сделать.

Если корневой элемент имеет индекс i, левый дочерний элемент находится в 2i, а правый дочерний элемент в 2i+1.

В массиве мы храним элементы из индекса 1.

Если мы храним элементы кучи, как это, мы можем непосредственно уменьшить элемент по индексу x и heapify от x.

Таким образом, мы используем o(logn) время. Для уменьшения это постоянно.