Как реализовать уменьшение ключа в куче Фибоначчи для запуска в O(1) амортизированное время?

Question

Как можно получить амортизированную сложность O(1) в операции уменьшения ключа в куче Фибоначчи? Простое нахождение узла в куче Фибоначчи, содержащей элемент, занимает O(n) времени с использованием BFS, что делает невозможным получение O(1) амортизированного времени.

Для справки, вот моя реализация BFS для поиска рассматриваемого узла:

   public fHeapNode search(int x){
       Stack<fHeapNode> stack = new Stack<fHeapNode>();
        stack.push(minNode);

        //Breath first searching
        while (!stack.empty()) {
            fHeapNode curr = stack.pop();

            if(curr.data==x) {return curr;}

            else{
                if (curr.child != null) {
                    stack.push(curr.child);
                }
                fHeapNode start = curr;
                curr = curr.right;

                while (curr != start) {

                    if (curr.child != null) {
                        stack.push(curr.child);
                    }
                    if(curr.data==x) {return curr;}
                    curr = curr.right;
                }

            }
        }  


        return null;


   }

А вот мой код для уменьшения ключа:

       public void decreaseKey(fHeapNode x, double k)
    {
        if (k > x.key) {
        //throw new IllegalArgumentException("entered value is wrong");
        }
        x.key = k;

        fHeapNode tempParent = x.parent;

        if ((tempParent != null) && (x.key < tempParent.key)) {
            cut(x,tempParent);
            cascadingCut(tempParent);
        }

        if (x.key < minNode.key) {
            minNode = x;
        }
    }

Answer 1

Обычно при реализации кучи Фибоначчи ваша реализация enqueue будет возвращать указатель на вновь вставленный узел. Таким образом, вы можете сохранить указатель для последующего использования. Вы абсолютно правы, что вам придется потратить O(n) времени на поиск узла, если у вас нет указателя на него.

В качестве примера, вот моя собственная реализация кучи Фибоначчи. enqueue метод дан здесь:

public Entry<T> enqueue(T value, double priority) {
     // ...
}

Обратите внимание, как он возвращает Entry<T> представляя этот узел. Соответствующая реализация decreaseKey имеет этот интерфейс:

public void decreaseKey(Entry<T> entry, double newPriority) {
     // ...
}

Здесь параметр является Entry<T> соответствует узлу, содержащему элемент, ключ которого должен быть уменьшен. Невозможно вызвать этот метод без Entry<T> который был возвращен enqueue потому что иначе это было бы невозможно эффективно реализовать.

Надеюсь это поможет!