1

フィボナッチ ヒープのキーの減少操作で 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;
        }
    }
4

1 に答える 1

0

通常、フィボナッチ ヒープを実装する場合、エンキューの実装は、新しく挿入されたノードへのポインターを返します。そうすれば、後で使用するためにポインタを保存できます。ノードへのポインターがない場合、ノードの検索に 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ことはできません。そうしないと、効率的に実装することが不可能になるからです。

お役に立てれば！

于 2013-10-22T07:32:15.710 に答える