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

通常，在实现斐波那契堆时，您的 enqueue 实现将返回一个指向新插入节点的指针。这样，您可以存储指针以供以后使用。如果您没有指向它的指针，您将不得不花费 O(n) 时间搜索节点，这是绝对正确的。

举个例子，这是我个人对 Fibonacci heap 的实现。方法在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 回答