如何實現斐波那契堆中的減鍵在O（1）攤銷時間內運行？

如何在Fibonacci堆的減鍵操作中獲得O（1）攤銷複雜性？只需在包含該元素的斐波那契堆中找到節點，就可以使用BFS執行O（n）個時間，這將導致無法獲得O（1）攤銷時間。如何實現斐波那契堆中的減鍵在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; 
     } 
    }

來源

2013-10-22 Rohit Garg

通常情況下，當實施一個斐波那契堆，你的enqueue實現會返回一個指向新插入節點的指針。這樣，您可以存儲指針供以後使用。如果你沒有指向它的指針，你絕對正確的做法是你必須花費O（n）次搜索節點。

作爲示例，這裏是my own personal implementation of a Fibonacci heap。該enqueue方法，這裏給出：

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

注意如何返回一個Entry<T>表示該節點。的decreaseKey相應的實現具有該接口：

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

這裏，參數是對應於保持其鍵應當減小的元件的節點處的Entry<T>。在沒有由enqueue返回的Entry<T>的情況下調用此方法是不可能的，否則將不可能有效地實現。

希望這會有所幫助！

來源

2013-10-22 07:32:15 templatetypedef

我可以通過製作一個headnodes的arraylist？所以你更新發生它會自動反映在arraylist以及因爲他們只是參考？我對麼？？ –

正因爲你提到的原因，在實現Prim算法時，保存一個包含所有堆節點的數組是很常見的。這將顯着加快速度。 – templatetypedef

謝謝！有效！ –

如何實現斐波那契堆中的減鍵在O（1）攤銷時間內運行？

回答

相關問題