斐波那契堆提取最小实现不起作用

Question

我正在实施 Fibonacci 堆来改进我的 Dijkstra 最短路径算法。我的插入方法工作正常，下一个我需要做的是 extract-min。我正在关注 CLRS。请注意本书中提到的一些属性还没有在我的实现中，因为到目前为止这些功能不需要它们，但我稍后会添加它们。

private static class FibonacciHeap {

    /**
     * Implementation of the node used in
     * fibonacci heap. The nodes are stored
     * as a circular doubly-linked list, making
     * delete and insert operations easy, as
     * well as being able to iterate through
     * without being forced to keep track of the
     * head
     */

    private class Node {

        /**
         * The vertex this node is storing
         */

        Vertex val;

        /**
         * Key used to know the order of vertices
         */

        int key;

        /**
         * The left and right sibling in the list
         */

        Node left, right;

        /**
         * Pointer to one of the child's
         */

        Node child;

        /**
         * The amount of children this node has
         */

        int degree;

        /**
         * Constructs a node with a value and key
         *
         * @param val the value of this node
         * @param key the key of this node
         */

        public Node(Vertex val, int key) {
            this.val = val;
            this.key = key;
        }

        /**
         * Inserts a new node into this node's list.
         * Inserts it to the left of this node, while
         * maintaining the fact that it's circular
         *
         * @param newNode The new node to be inserted
         */

        public void insert(Node newNode) {
            newNode.left = left;
            left.right = newNode;
            newNode.right = this;
            left = newNode;
            if(newNode.key < min.key) {
                min = newNode;
            }

            size++;
        }

        /**
         * Removes this node from it's list
         */

        public void remove() {
            right.left = left;
            left.right = right;
        }

        /**
         * Inserts a new child into this nodes
         * child list
         *
         * @param child The new node to be added as a child
         */

        public void link(Node child) {
            child.remove();

            if(this.child == null) {
                this.child = child;
            } else {
                this.child.insert(child);
            }

            degree ++;
        }

        /**
         * Used for debugging. Will be removed after
         * all operations work fine
         *
         * @return A string representation of this node
         */

        @Override
        public String toString() {
            Node dummy = right;
            StringBuilder sb = new StringBuilder();

            sb.append(key).append(" -> (");
            sb.append(dummy.child);
            sb.append(") ");

            while(dummy != this) {
                sb.append(dummy.key).append(" -> (");
                sb.append(dummy.child);
                sb.append(") ");
                dummy = dummy.right;
            }

            return sb.toString();
        }
    }

    /**
     * Pointer to the node with the smallest key
     */

    private Node min;

    /**
     * Stores the number of nodes in the heap
     */

    private int size;

    /**
     * Creates an empty Fibonacci Heap
     */

    public FibonacciHeap() { }

    /**
     * Gets and returns the key with the
     * smallest value
     *
     * @return the key with the smallest value
     */

    public int getMin() {
        if(min == null) {
            throw new NoSuchElementException("Empty Fibonacci Heap");
        }

        return min.key;
    }

    /**
     * Inserts a vertex along with a key. The
     * key is the one used to measure whether
     * this vertex is lesser than another
     * 
     * @param vertex vertex to be added
     * @param key key of the vertex
     */

    public void insert(Vertex vertex, int key) {
        if(min == null) {
            min = new Node(vertex, key);
            min.left = min;
            min.right = min;
            size = 1;
        } else {
            min.insert(new Node(vertex, key));
        }
    }

    /**
     * Removes the node with the smallest key from
     * the heap, and updates the minimum node if needed
     *
     * @return The node with the smallest key prior to this method call
     */

    public Vertex extractMin() {
        if(isEmpty()) {
            throw new NoSuchElementException("Empty Fibonacci Heap");
        }

        Vertex toReturn;

        if(min == null) {
            toReturn = null;
        } else {
            toReturn = min.val;

            if(min.right == min) {
                min = null;
            } else {
                min.remove();
                min = min.right;
                consolidate();
            }
        }

        return toReturn;
    }

    /**
     * Consolidates the heap. Consolidation is the process
     * making every node in the root list have it's own
     * unique degree. That is, every node in the top most
     * layer has a unique amount of children
     */

    private void consolidate() {
        Node[] degrees = new Node[size];
        degrees[min.degree] = min;
        Node tempMin, dummy = (tempMin = min).right;

        while(dummy != tempMin) {
            if(dummy.key < min.key) {
                min = dummy;
            }

            while(degrees[dummy.degree] != null) {
                Node other = degrees[dummy.degree];

                if(other.key < dummy.key) {
                    Node temp = dummy;
                    dummy = other;
                    other = temp;
                }

                dummy.link(other);
                degrees[dummy.degree - 1] = null;
            }

            degrees[dummy.degree] = dummy;
        }
    }

    /**
     * Returns true if and only if the
     * heap is empty
     *
     * @return if the heap is empty
     */

    public boolean isEmpty() {
        return min == null;
    }

    /**
     * A string representation of this
     * heap. Format of string is:
     * node1 -> (node1.child.toString()) node2 -> (node2.child.toString()) ... noden -> (noden.child.toString())
     * The string representation of the
     * heap is the string representation of
     * the minimum node
     *
     * @return A string representation of this heap
     */

    @Override
    public String toString() {
        return min.toString();
    }

}

这是它给出的堆栈跟踪：

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 10 out of bounds for length 10
    at GraphTheory.ShortestPathAlgorithms.DijkstraShortestPath$FibonacciHeap.consolidate(DijkstraShortestPath.java:362)
    at GraphTheory.ShortestPathAlgorithms.DijkstraShortestPath$FibonacciHeap.extractMin(DijkstraShortestPath.java:338)
    at GraphTheory.ShortestPathAlgorithms.DijkstraShortestPath.main(DijkstraShortestPath.java:104)

主要错误在consolidate函数中while循环的内层条件语句。我还在代码中注释了这一行。出了什么问题？我的主要测试方法是从1-10中插入10个随机数，然后提取最小值直到为空。第一次调用 extract-min 时出现错误。

public static void main(String[] args) {
    FibonacciHeap f = new FibonacciHeap();
    StringBuilder sb = new StringBuilder();

    for(int i = 0; i < 10; i ++) {
        f.insert(new Vertex(i), (int) (Math.random() * 10));
    }

    while(!f.isEmpty()) {
        System.out.println(f.extractMin());
    }
}

Answer 1

无法查明确切的错误。但是，我可以根据经验告诉你，你不应该在巩固的时候找到最小值。你合并，然后你找到新的最小值。当您有多个具有相同键的节点并且 min 指向的节点没有出现在根列表中时，您可能会遇到麻烦。

此外，在测试时，不要使用随机函数。创建一个任意数字的数组，并将数组中的元素插入堆中。

我也不明白你的实现是如何处理 Fib 堆中只有一个堆有序树的。那么当你执行 extract-min 时会发生什么？

如果需要，您可以找到我的 Python 实现 here。