Fibonacci 힙에서 감소 키를 구현하여 O (1) 상각 시간에 실행하는 방법은 무엇입니까?

Question

피보나치 힙의 감소 키 작업에서 O (1) 상각 된 복잡성을 어떻게 얻을 수 있습니까? 요소가 포함 된 피보나치 힙의 노드를 찾는 것은 BFS를 사용하여 O (n) 시간이 걸리므로 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) 시간 동안 노드를 검색해야만한다는 것이 옳다. 예 : my own personal implementation of a Fibonacci heapenqueue 방법은 여기에 주어집니다 :

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

공지 사항은 해당 노드를 나타내는 Entry<T>을 반환하는 방법. 여기

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

이 파라미터 키 감소되어야 할 요소를 유지하는 노드에 대응하는 Entry<T>이다 decreaseKey의 대응하는 구현은이 인터페이스를 갖는다. 이 enqueue으로 반환되지 않고이 메서드를 호출하는 것은 불가능합니다. 그렇지 않으면 효율적으로 구현할 수 없기 때문입니다.

희망이 도움이됩니다.