英文:
Fibonacci Heap Extract Min Implementation Not Working
问题
我正在实现斐波那契堆来优化我的Dijkstra最短路径算法。我的插入方法运行良好，下一步需要完成的是提取最小值。我正在遵循CLRS的方法。请注意，书中提到的一些属性尚未包含在我的实现中，因为它们目前的函数中还不需要，但我稍后会添加它们。
以下是你提供的代码的翻译：
private static class FibonacciHeap {
/**
* 在斐波那契堆中使用的节点的实现。
* 节点被存储为一个循环双向链表，这使得
* 删除和插入操作都很容易，还可以在不强制
* 追踪头部的情况下进行迭代。
*/
private class Node {
/**
* 该节点存储的顶点
*/
Vertex val;
/**
* 用于确定顶点顺序的键
*/
int key;
/**
* 列表中的左兄弟和右兄弟
*/
Node left, right;
/**
* 指向一个子节点的指针
*/
Node child;
/**
* 该节点拥有的子节点数量
*/
int degree;
/**
* 使用值和键构造节点
*
* @param val 该节点的值
* @param key 该节点的键
*/
public Node(Vertex val, int key) {
this.val = val;
this.key = key;
}
/**
* 将新节点插入到此节点的列表中。
* 将其插入到此节点的左侧，同时保持其循环性质。
*
* @param newNode 要插入的新节点
*/
public void insert(Node newNode) {
newNode.left = left;
left.right = newNode;
newNode.right = this;
left = newNode;
if(newNode.key < min.key) {
min = newNode;
}
size++;
}
/**
* 从其列表中移除此节点
*/
public void remove() {
right.left = left;
left.right = right;
}
/**
* 将一个新的子节点插入到此节点的子节点列表中
*
* @param child 要添加为子节点的新节点
*/
public void link(Node child) {
child.remove();
if(this.child == null) {
this.child = child;
} else {
this.child.insert(child);
}
degree ++;
}
/**
* 用于调试的方法，所有操作正常后将被移除
*
* @return 此节点的字符串表示形式
*/
@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();
}
}
/**
* 指向具有最小键的节点
*/
private Node min;
/**
* 堆中节点的数量
*/
private int size;
/**
* 创建一个空的斐波那契堆
*/
public FibonacciHeap() { }
/**
* 获取并返回具有最小值的键
*
* @return 具有最小值的键
*/
public int getMin() {
if(min == null) {
throw new NoSuchElementException("空斐波那契堆");
}
return min.key;
}
/**
* 插入一个顶点及其键。键用于衡量是否
* 此顶点小于另一个顶点
*
* @param vertex 要添加的顶点
* @param key 顶点的键
*/
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));
}
}
/**
* 从堆中移除具有最小键的节点，并在需要时更新最小节点
*
* @return 在调用此方法之前具有最小键的节点
*/
public Vertex extractMin() {
if(isEmpty()) {
throw new NoSuchElementException("空斐波那契堆");
}
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;
}
/**
* 合并堆。合并是使根列表中的每个节点
* 具有其自己的唯一度数的过程。
*/
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;
}
}
/**
* 当且仅当堆为空时返回true
*
* @return 如果堆为空，则为true
*/
public boolean isEmpty() {
return min == null;
}
/**
* 此堆的字符串表示形式。字符串格式为：
* 节点1 -> (节点1.child.toString()) 节点2 -> (节点2.child.toString()) ... 节点n -> (节点n.child.toString())
* 堆的字符串表示形式是最小节点的字符串表示形式
*
* @return 此堆的字符串表示形式
*/
@Override
public String toString
<details>
<summary>英文:</summary>
I am implementing Fibonacci Heap to improve on my Dijkstra's shortest path algorithm. My insert method works fine, and the next one I needed to do is extract-min. I am following CLRS. Please note some attributes mentioned in the book aren't in my implementation yet, as they are not needed for the functions so far, but I will add them later.
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();
}
}
This is the stack trace that it gives:
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)
The main error is given in the conditional statement of the inner while loop in the consolidate function. I also commented the line in the code. What is going wrong? My main testing method insert 10 random numbers from 1 - 10, and then extracts the minimum until it's empty. The error occurs the first time extract-min is called.
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());
}
}
</details>
# 答案1
**得分**: 1
无法精确定位具体错误。但是，根据经验我可以告诉你，在合并时不应该寻找最小值。你先合并，然后再寻找新的最小值。当有多个具有相同键的节点，并且被 `min` 指向的节点没有出现在根列表中时，可能会出问题。
另外，在测试时，不要使用随机函数。创建一个包含任意数字的数组，然后将数组中的元素插入堆中。
我还不明白你的实现如何处理只有一个堆有序树的情况。当执行 `extract-min` 时会发生什么呢？
如果需要，你可以在[这里][1]找到我的Python实现。
[1]: https://github.com/arunkumaraqm/Prims-Algorithm-Using-Fibonacci-Heap
<details>
<summary>英文:</summary>
Can't pinpoint the exact bug. But, I can tell you from experience that you should not find the minimum while consolidating. You consolidate and then you find the new minimum. You might get into trouble when you have multiple nodes with the same key and the one pointed to by `min` doesn't end up in the root list.
Also, while testing, don't use a random function. Create an array of arbitrary numbers and insert elements from the array into the heap.
I also don't understand how your implementation handles there being only one heap ordered tree in the Fib heap. What happens when you do an `extract-min` then?
You can find my Python implementation [here][1] if you need it.
[1]: https://github.com/arunkumaraqm/Prims-Algorithm-Using-Fibonacci-Heap
</details>
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论