斐波那契堆实现不起作用
Fibonacci Heap implementation is not working
我一直在尝试理解 Fibonacci 堆实现代码 here 并尝试使用似乎不起作用的简单测试用例进行测试。我插入了3个节点，然后每次都打印最小值，但答案是错误的。
public static void main(String[] args) {
FibonacciHeap<Integer> node = new FibonacciHeap<Integer>();
if(node.isEmpty()) System.out.println("Empty");
else System.out.println("Not empty");
node.enqueue(10,1);
System.out.println((node.min()).getValue()); // Should print 10
node.enqueue(5,1);
System.out.println((node.min()).getValue()); // Should print 5
node.enqueue(7,1);
System.out.println((node.min()).getValue()); // Should print 5
}
预期的输出应该是
Empty
10
5
5
但是上面代码的实际输出是
Empty
10
5
7
谁能告诉我哪里做错了。是实现错误还是我没有正确理解代码？
编辑 - 1：添加了下面的整个代码：
/***********************************************************************
* File: FibonacciHeap.java
* Author: Keith Schwarz (htiek@cs.stanford.edu)
*
* An implementation of a priority queue backed by a Fibonacci heap,
* as described by Fredman and Tarjan. Fibonacci heaps are interesting
* theoretically because they have asymptotically good runtime guarantees
* for many operations. In particular, insert, peek, and decrease-key all
* run in amortized O(1) time. dequeueMin and delete each run in amortized
* O(lg n) time. This allows algorithms that rely heavily on decrease-key
* to gain significant performance boosts. For example, Dijkstra's algorithm
* for single-source shortest paths can be shown to run in O(m + n lg n) using
* a Fibonacci heap, compared to O(m lg n) using a standard binary or binomial
* heap.
*
* Internally, a Fibonacci heap is represented as a circular, doubly-linked
* list of trees obeying the min-heap property. Each node stores pointers
* to its parent (if any) and some arbitrary child. Additionally, every
* node stores its degree (the number of children it has) and whether it
* is a "marked" node. Finally, each Fibonacci heap stores a pointer to
* the tree with the minimum value.
*
* To insert a node into a Fibonacci heap, a singleton tree is created and
* merged into the rest of the trees. The merge operation works by simply
* splicing together the doubly-linked lists of the two trees, then updating
* the min pointer to be the smaller of the minima of the two heaps. Peeking
* at the smallest element can therefore be accomplished by just looking at
* the min element. All of these operations complete in O(1) time.
*
* The tricky operations are dequeueMin and decreaseKey. dequeueMin works
* by removing the root of the tree containing the smallest element, then
* merging its children with the topmost roots. Then, the roots are scanned
* and merged so that there is only one tree of each degree in the root list.
* This works by maintaining a dynamic array of trees, each initially null,
* pointing to the roots of trees of each dimension. The list is then scanned
* and this array is populated. Whenever a conflict is discovered, the
* appropriate trees are merged together until no more conflicts exist. The
* resulting trees are then put into the root list. A clever analysis using
* the potential method can be used to show that the amortized cost of this
* operation is O(lg n), see "Introduction to Algorithms, Second Edition" by
* Cormen, Rivest, Leiserson, and Stein for more details.
*
* The other hard operation is decreaseKey, which works as follows. First, we
* update the key of the node to be the new value. If this leaves the node
* smaller than its parent, we're done. Otherwise, we cut the node from its
* parent, add it as a root, and then mark its parent. If the parent was
* already marked, we cut that node as well, recursively mark its parent,
* and continue this process. This can be shown to run in O(1) amortized time
* using yet another clever potential function. Finally, given this function,
* we can implement delete by decreasing a key to -\infty, then calling
* dequeueMin to extract it.
*/
import java.util.*;
public final class FibonacciHeap<T> {
/** In order for all of the Fibonacci heap operations to complete in O(1),
* clients need to have O(1) access to any element in the heap. We make
* this work by having each insertion operation produce a handle to the
* node in the tree. In actuality, this handle is the node itself, but
* we guard against external modification by marking the internal fields
* private.
*/
public static final class Entry<T> {
private int mDegree = 0;
private boolean mIsMarked = false;
private Entry<T> mNext;
private Entry<T> mPrev;
private Entry<T> mParent;
private Entry<T> mChild;
private T mElem;
private double mPriority;
/**
* Returns the element represented by this heap entry.
*
* @return The element represented by this heap entry.
*/
public T getValue() {
return mElem;
}
/**
* Sets the element associated with this heap entry.
*
* @param value The element to associate with this heap entry.
*/
public void setValue(T value) {
mElem = value;
}
/**
* Returns the priority of this element.
*
* @return The priority of this element.
*/
public double getPriority() {
return mPriority;
}
/**
* Constructs a new Entry that holds the given element with the indicated
* priority.
*
* @param elem The element stored in this node.
* @param priority The priority of this element.
*/
private Entry(T elem, double priority) {
mNext = mPrev = this;
mElem = elem;
mPriority = priority;
}
}
/* Pointer to the minimum element in the heap. */
private Entry<T> mMin = null;
/* Cached size of the heap, so we don't have to recompute this explicitly. */
private int mSize = 0;
/**
* Inserts the specified element into the Fibonacci heap with the specified
* priority. Its priority must be a valid double, so you cannot set the
* priority to NaN.
*
* @param value The value to insert.
* @param priority Its priority, which must be valid.
* @return An Entry representing that element in the tree.
*/
public Entry<T> enqueue(T value, double priority) {
checkPriority(priority);
/* Create the entry object, which is a circularly-linked list of length
* one.
*/
Entry<T> result = new Entry<T>(value, priority);
/* Merge this singleton list with the tree list. */
mMin = mergeLists(mMin, result);
/* Increase the size of the heap; we just added something. */
++mSize;
/* Return the reference to the new element. */
return result;
}
/**
* Returns an Entry object corresponding to the minimum element of the
* Fibonacci heap, throwing a NoSuchElementException if the heap is
* empty.
*
* @return The smallest element of the heap.
* @throws NoSuchElementException If the heap is empty.
*/
public Entry<T> min() {
if (isEmpty())
throw new NoSuchElementException("Heap is empty.");
return mMin;
}
/**
* Returns whether the heap is empty.
*
* @return Whether the heap is empty.
*/
public boolean isEmpty() {
return mMin == null;
}
/**
* Returns the number of elements in the heap.
*
* @return The number of elements in the heap.
*/
public int size() {
return mSize;
}
/**
* Given two Fibonacci heaps, returns a new Fibonacci heap that contains
* all of the elements of the two heaps. Each of the input heaps is
* destructively modified by having all its elements removed. You can
* continue to use those heaps, but be aware that they will be empty
* after this call completes.
*
* @param one The first Fibonacci heap to merge.
* @param two The second Fibonacci heap to merge.
* @return A new FibonacciHeap containing all of the elements of both
* heaps.
*/
public static <T> FibonacciHeap<T> merge(FibonacciHeap<T> one, FibonacciHeap<T> two) {
/* Create a new FibonacciHeap to hold the result. */
FibonacciHeap<T> result = new FibonacciHeap<T>();
/* Merge the two Fibonacci heap root lists together. This helper function
* also computes the min of the two lists, so we can store the result in
* the mMin field of the new heap.
*/
result.mMin = mergeLists(one.mMin, two.mMin);
/* The size of the new heap is the sum of the sizes of the input heaps. */
result.mSize = one.mSize + two.mSize;
/* Clear the old heaps. */
one.mSize = two.mSize = 0;
one.mMin = null;
two.mMin = null;
/* Return the newly-merged heap. */
return result;
}
/**
* Dequeues and returns the minimum element of the Fibonacci heap. If the
* heap is empty, this throws a NoSuchElementException.
*
* @return The smallest element of the Fibonacci heap.
* @throws NoSuchElementException If the heap is empty.
*/
public Entry<T> dequeueMin() {
/* Check for whether we're empty. */
if (isEmpty())
throw new NoSuchElementException("Heap is empty.");
/* Otherwise, we're about to lose an element, so decrement the number of
* entries in this heap.
*/
--mSize;
/* Grab the minimum element so we know what to return. */
Entry<T> minElem = mMin;
/* Now, we need to get rid of this element from the list of roots. There
* are two cases to consider. First, if this is the only element in the
* list of roots, we set the list of roots to be null by clearing mMin.
* Otherwise, if it's not null, then we write the elements next to the
* min element around the min element to remove it, then arbitrarily
* reassign the min.
*/
if (mMin.mNext == mMin) { // Case one
mMin = null;
}
else { // Case two
mMin.mPrev.mNext = mMin.mNext;
mMin.mNext.mPrev = mMin.mPrev;
mMin = mMin.mNext; // Arbitrary element of the root list.
}
/* Next, clear the parent fields of all of the min element's children,
* since they're about to become roots. Because the elements are
* stored in a circular list, the traversal is a bit complex.
*/
if (minElem.mChild != null) {
/* Keep track of the first visited node. */
Entry<?> curr = minElem.mChild;
do {
curr.mParent = null;
/* Walk to the next node, then stop if this is the node we
* started at.
*/
curr = curr.mNext;
} while (curr != minElem.mChild);
}
/* Next, splice the children of the root node into the topmost list,
* then set mMin to point somewhere in that list.
*/
mMin = mergeLists(mMin, minElem.mChild);
/* If there are no entries left, we're done. */
if (mMin == null) return minElem;
/* Next, we need to coalsce all of the roots so that there is only one
* tree of each degree. To track trees of each size, we allocate an
* ArrayList where the entry at position i is either null or the
* unique tree of degree i.
*/
List<Entry<T>> treeTable = new ArrayList<Entry<T>>();
/* We need to traverse the entire list, but since we're going to be
* messing around with it we have to be careful not to break our
* traversal order mid-stream. One major challenge is how to detect
* whether we're visiting the same node twice. To do this, we'll
* spent a bit of overhead adding all of the nodes to a list, and
* then will visit each element of this list in order.
*/
List<Entry<T>> toVisit = new ArrayList<Entry<T>>();
/* To add everything, we'll iterate across the elements until we
* find the first element twice. We check this by looping while the
* list is empty or while the current element isn't the first element
* of that list.
*/
for (Entry<T> curr = mMin; toVisit.isEmpty() || toVisit.get(0) != curr; curr = curr.mNext)
toVisit.add(curr);
/* Traverse this list and perform the appropriate unioning steps. */
for (Entry<T> curr: toVisit) {
/* Keep merging until a match arises. */
while (true) {
/* Ensure that the list is long enough to hold an element of this
* degree.
*/
while (curr.mDegree >= treeTable.size())
treeTable.add(null);
/* If nothing's here, we're can record that this tree has this size
* and are done processing.
*/
if (treeTable.get(curr.mDegree) == null) {
treeTable.set(curr.mDegree, curr);
break;
}
/* Otherwise, merge with what's there. */
Entry<T> other = treeTable.get(curr.mDegree);
treeTable.set(curr.mDegree, null); // Clear the slot
/* Determine which of the two trees has the smaller root, storing
* the two tree accordingly.
*/
Entry<T> min = (other.mPriority < curr.mPriority)? other : curr;
Entry<T> max = (other.mPriority < curr.mPriority)? curr : other;
/* Break max out of the root list, then merge it into min's child
* list.
*/
max.mNext.mPrev = max.mPrev;
max.mPrev.mNext = max.mNext;
/* Make it a singleton so that we can merge it. */
max.mNext = max.mPrev = max;
min.mChild = mergeLists(min.mChild, max);
/* Reparent max appropriately. */
max.mParent = min;
/* Clear max's mark, since it can now lose another child. */
max.mIsMarked = false;
/* Increase min's degree; it now has another child. */
++min.mDegree;
/* Continue merging this tree. */
curr = min;
}
/* Update the global min based on this node. Note that we compare
* for <= instead of < here. That's because if we just did a
* reparent operation that merged two different trees of equal
* priority, we need to make sure that the min pointer points to
* the root-level one.
*/
if (curr.mPriority <= mMin.mPriority) mMin = curr;
}
return minElem;
}
/**
* Decreases the key of the specified element to the new priority. If the
* new priority is greater than the old priority, this function throws an
* IllegalArgumentException. The new priority must be a finite double,
* so you cannot set the priority to be NaN, or +/- infinity. Doing
* so also throws an IllegalArgumentException.
*
* It is assumed that the entry belongs in this heap. For efficiency
* reasons, this is not checked at runtime.
*
* @param entry The element whose priority should be decreased.
* @param newPriority The new priority to associate with this entry.
* @throws IllegalArgumentException If the new priority exceeds the old
* priority, or if the argument is not a finite double.
*/
public void decreaseKey(Entry<T> entry, double newPriority) {
checkPriority(newPriority);
if (newPriority > entry.mPriority)
throw new IllegalArgumentException("New priority exceeds old.");
/* Forward this to a helper function. */
decreaseKeyUnchecked(entry, newPriority);
}
/**
* Deletes this Entry from the Fibonacci heap that contains it.
*
* It is assumed that the entry belongs in this heap. For efficiency
* reasons, this is not checked at runtime.
*
* @param entry The entry to delete.
*/
public void delete(Entry<T> entry) {
/* Use decreaseKey to drop the entry's key to -infinity. This will
* guarantee that the node is cut and set to the global minimum.
*/
decreaseKeyUnchecked(entry, Double.NEGATIVE_INFINITY);
/* Call dequeueMin to remove it. */
dequeueMin();
}
/**
* Utility function which, given a user-specified priority, checks whether
* it's a valid double and throws an IllegalArgumentException otherwise.
*
* @param priority The user's specified priority.
* @throws IllegalArgumentException If it is not valid.
*/
private void checkPriority(double priority) {
if (Double.isNaN(priority))
throw new IllegalArgumentException(priority + " is invalid.");
}
/**
* Utility function which, given two pointers into disjoint circularly-
* linked lists, merges the two lists together into one circularly-linked
* list in O(1) time. Because the lists may be empty, the return value
* is the only pointer that's guaranteed to be to an element of the
* resulting list.
*
* This function assumes that one and two are the minimum elements of the
* lists they are in, and returns a pointer to whichever is smaller. If
* this condition does not hold, the return value is some arbitrary pointer
* into the doubly-linked list.
*
* @param one A pointer into one of the two linked lists.
* @param two A pointer into the other of the two linked lists.
* @return A pointer to the smallest element of the resulting list.
*/
private static <T> Entry<T> mergeLists(Entry<T> one, Entry<T> two) {
/* There are four cases depending on whether the lists are null or not.
* We consider each separately.
*/
if (one == null && two == null) { // Both null, resulting list is null.
return null;
}
else if (one != null && two == null) { // Two is null, result is one.
return one;
}
else if (one == null && two != null) { // One is null, result is two.
return two;
}
else { // Both non-null; actually do the splice.
/* This is actually not as easy as it seems. The idea is that we'll
* have two lists that look like this:
*
* +----+ +----+ +----+
* | |--N->|one |--N->| |
* | |<-P--| |<-P--| |
* +----+ +----+ +----+
*
*
* +----+ +----+ +----+
* | |--N->|two |--N->| |
* | |<-P--| |<-P--| |
* +----+ +----+ +----+
*
* And we want to relink everything to get
*
* +----+ +----+ +----+---+
* | |--N->|one | | | |
* | |<-P--| | | |<+ |
* +----+ +----+<-\ +----+ | |
* \ P | |
* N \ N |
* +----+ +----+ \->+----+ | |
* | |--N->|two | | | | |
* | |<-P--| | | | | P
* +----+ +----+ +----+ | |
* ^ | | |
* | +-------------+ |
* +-----------------+
*
*/
Entry<T> oneNext = one.mNext; // Cache this since we're about to overwrite it.
one.mNext = two.mNext;
one.mNext.mPrev = one;
two.mNext = oneNext;
two.mNext.mPrev = two;
/* Return a pointer to whichever's smaller. */
return one.mPriority < two.mPriority? one : two;
}
}
/**
* Decreases the key of a node in the tree without doing any checking to ensure
* that the new priority is valid.
*
* @param entry The node whose key should be decreased.
* @param priority The node's new priority.
*/
private void decreaseKeyUnchecked(Entry<T> entry, double priority) {
/* First, change the node's priority. */
entry.mPriority = priority;
/* If the node no longer has a higher priority than its parent, cut it.
* Note that this also means that if we try to run a delete operation
* that decreases the key to -infinity, it's guaranteed to cut the node
* from its parent.
*/
if (entry.mParent != null && entry.mPriority <= entry.mParent.mPriority)
cutNode(entry);
/* If our new value is the new min, mark it as such. Note that if we
* ended up decreasing the key in a way that ties the current minimum
* priority, this will change the min accordingly.
*/
if (entry.mPriority <= mMin.mPriority)
mMin = entry;
}
/**
* Cuts a node from its parent. If the parent was already marked, recursively
* cuts that node from its parent as well.
*
* @param entry The node to cut from its parent.
*/
private void cutNode(Entry<T> entry) {
/* Begin by clearing the node's mark, since we just cut it. */
entry.mIsMarked = false;
/* Base case: If the node has no parent, we're done. */
if (entry.mParent == null) return;
/* Rewire the node's siblings around it, if it has any siblings. */
if (entry.mNext != entry) { // Has siblings
entry.mNext.mPrev = entry.mPrev;
entry.mPrev.mNext = entry.mNext;
}
/* If the node is the one identified by its parent as its child,
* we need to rewrite that pointer to point to some arbitrary other
* child.
*/
if (entry.mParent.mChild == entry) {
/* If there are any other children, pick one of them arbitrarily. */
if (entry.mNext != entry) {
entry.mParent.mChild = entry.mNext;
}
/* Otherwise, there aren't any children left and we should clear the
* pointer and drop the node's degree.
*/
else {
entry.mParent.mChild = null;
}
}
/* Decrease the degree of the parent, since it just lost a child. */
--entry.mParent.mDegree;
/* Splice this tree into the root list by converting it to a singleton
* and invoking the merge subroutine.
*/
entry.mPrev = entry.mNext = entry;
mMin = mergeLists(mMin, entry);
/* Mark the parent and recursively cut it if it's already been
* marked.
*/
if (entry.mParent.mIsMarked)
cutNode(entry.mParent);
else
entry.mParent.mIsMarked = true;
/* Clear the relocated node's parent; it's now a root. */
entry.mParent = null;
}
public static void main(String[] args) {
FibonacciHeap<Integer> node = new FibonacciHeap<Integer>();
if(node.isEmpty()) System.out.println("Empty");
else System.out.println("Not empty");
node.enqueue(10,1);
System.out.println((node.min()).getValue());
node.enqueue(5,1);
System.out.println((node.min()).getValue());
node.enqueue(7,1);
System.out.println((node.min()).getValue());
}
}
如果您查看 mergeLists 方法，它使用此行 return mMin:
/* Return a pointer to whichever's smaller. */
return one.mPriority < two.mPriority? one : two;
因此，当您将 7 排入队列时，因为它与 5 具有相同的优先级，所以当您调用 min() 时，它 return 是 7。
我一直在尝试理解 Fibonacci 堆实现代码 here 并尝试使用似乎不起作用的简单测试用例进行测试。我插入了3个节点，然后每次都打印最小值，但答案是错误的。
public static void main(String[] args) {
FibonacciHeap<Integer> node = new FibonacciHeap<Integer>();
if(node.isEmpty()) System.out.println("Empty");
else System.out.println("Not empty");
node.enqueue(10,1);
System.out.println((node.min()).getValue()); // Should print 10
node.enqueue(5,1);
System.out.println((node.min()).getValue()); // Should print 5
node.enqueue(7,1);
System.out.println((node.min()).getValue()); // Should print 5
}
预期的输出应该是
Empty
10
5
5
但是上面代码的实际输出是
Empty
10
5
7
谁能告诉我哪里做错了。是实现错误还是我没有正确理解代码？
编辑 - 1：添加了下面的整个代码：
/***********************************************************************
* File: FibonacciHeap.java
* Author: Keith Schwarz (htiek@cs.stanford.edu)
*
* An implementation of a priority queue backed by a Fibonacci heap,
* as described by Fredman and Tarjan. Fibonacci heaps are interesting
* theoretically because they have asymptotically good runtime guarantees
* for many operations. In particular, insert, peek, and decrease-key all
* run in amortized O(1) time. dequeueMin and delete each run in amortized
* O(lg n) time. This allows algorithms that rely heavily on decrease-key
* to gain significant performance boosts. For example, Dijkstra's algorithm
* for single-source shortest paths can be shown to run in O(m + n lg n) using
* a Fibonacci heap, compared to O(m lg n) using a standard binary or binomial
* heap.
*
* Internally, a Fibonacci heap is represented as a circular, doubly-linked
* list of trees obeying the min-heap property. Each node stores pointers
* to its parent (if any) and some arbitrary child. Additionally, every
* node stores its degree (the number of children it has) and whether it
* is a "marked" node. Finally, each Fibonacci heap stores a pointer to
* the tree with the minimum value.
*
* To insert a node into a Fibonacci heap, a singleton tree is created and
* merged into the rest of the trees. The merge operation works by simply
* splicing together the doubly-linked lists of the two trees, then updating
* the min pointer to be the smaller of the minima of the two heaps. Peeking
* at the smallest element can therefore be accomplished by just looking at
* the min element. All of these operations complete in O(1) time.
*
* The tricky operations are dequeueMin and decreaseKey. dequeueMin works
* by removing the root of the tree containing the smallest element, then
* merging its children with the topmost roots. Then, the roots are scanned
* and merged so that there is only one tree of each degree in the root list.
* This works by maintaining a dynamic array of trees, each initially null,
* pointing to the roots of trees of each dimension. The list is then scanned
* and this array is populated. Whenever a conflict is discovered, the
* appropriate trees are merged together until no more conflicts exist. The
* resulting trees are then put into the root list. A clever analysis using
* the potential method can be used to show that the amortized cost of this
* operation is O(lg n), see "Introduction to Algorithms, Second Edition" by
* Cormen, Rivest, Leiserson, and Stein for more details.
*
* The other hard operation is decreaseKey, which works as follows. First, we
* update the key of the node to be the new value. If this leaves the node
* smaller than its parent, we're done. Otherwise, we cut the node from its
* parent, add it as a root, and then mark its parent. If the parent was
* already marked, we cut that node as well, recursively mark its parent,
* and continue this process. This can be shown to run in O(1) amortized time
* using yet another clever potential function. Finally, given this function,
* we can implement delete by decreasing a key to -\infty, then calling
* dequeueMin to extract it.
*/
import java.util.*;
public final class FibonacciHeap<T> {
/** In order for all of the Fibonacci heap operations to complete in O(1),
* clients need to have O(1) access to any element in the heap. We make
* this work by having each insertion operation produce a handle to the
* node in the tree. In actuality, this handle is the node itself, but
* we guard against external modification by marking the internal fields
* private.
*/
public static final class Entry<T> {
private int mDegree = 0;
private boolean mIsMarked = false;
private Entry<T> mNext;
private Entry<T> mPrev;
private Entry<T> mParent;
private Entry<T> mChild;
private T mElem;
private double mPriority;
/**
* Returns the element represented by this heap entry.
*
* @return The element represented by this heap entry.
*/
public T getValue() {
return mElem;
}
/**
* Sets the element associated with this heap entry.
*
* @param value The element to associate with this heap entry.
*/
public void setValue(T value) {
mElem = value;
}
/**
* Returns the priority of this element.
*
* @return The priority of this element.
*/
public double getPriority() {
return mPriority;
}
/**
* Constructs a new Entry that holds the given element with the indicated
* priority.
*
* @param elem The element stored in this node.
* @param priority The priority of this element.
*/
private Entry(T elem, double priority) {
mNext = mPrev = this;
mElem = elem;
mPriority = priority;
}
}
/* Pointer to the minimum element in the heap. */
private Entry<T> mMin = null;
/* Cached size of the heap, so we don't have to recompute this explicitly. */
private int mSize = 0;
/**
* Inserts the specified element into the Fibonacci heap with the specified
* priority. Its priority must be a valid double, so you cannot set the
* priority to NaN.
*
* @param value The value to insert.
* @param priority Its priority, which must be valid.
* @return An Entry representing that element in the tree.
*/
public Entry<T> enqueue(T value, double priority) {
checkPriority(priority);
/* Create the entry object, which is a circularly-linked list of length
* one.
*/
Entry<T> result = new Entry<T>(value, priority);
/* Merge this singleton list with the tree list. */
mMin = mergeLists(mMin, result);
/* Increase the size of the heap; we just added something. */
++mSize;
/* Return the reference to the new element. */
return result;
}
/**
* Returns an Entry object corresponding to the minimum element of the
* Fibonacci heap, throwing a NoSuchElementException if the heap is
* empty.
*
* @return The smallest element of the heap.
* @throws NoSuchElementException If the heap is empty.
*/
public Entry<T> min() {
if (isEmpty())
throw new NoSuchElementException("Heap is empty.");
return mMin;
}
/**
* Returns whether the heap is empty.
*
* @return Whether the heap is empty.
*/
public boolean isEmpty() {
return mMin == null;
}
/**
* Returns the number of elements in the heap.
*
* @return The number of elements in the heap.
*/
public int size() {
return mSize;
}
/**
* Given two Fibonacci heaps, returns a new Fibonacci heap that contains
* all of the elements of the two heaps. Each of the input heaps is
* destructively modified by having all its elements removed. You can
* continue to use those heaps, but be aware that they will be empty
* after this call completes.
*
* @param one The first Fibonacci heap to merge.
* @param two The second Fibonacci heap to merge.
* @return A new FibonacciHeap containing all of the elements of both
* heaps.
*/
public static <T> FibonacciHeap<T> merge(FibonacciHeap<T> one, FibonacciHeap<T> two) {
/* Create a new FibonacciHeap to hold the result. */
FibonacciHeap<T> result = new FibonacciHeap<T>();
/* Merge the two Fibonacci heap root lists together. This helper function
* also computes the min of the two lists, so we can store the result in
* the mMin field of the new heap.
*/
result.mMin = mergeLists(one.mMin, two.mMin);
/* The size of the new heap is the sum of the sizes of the input heaps. */
result.mSize = one.mSize + two.mSize;
/* Clear the old heaps. */
one.mSize = two.mSize = 0;
one.mMin = null;
two.mMin = null;
/* Return the newly-merged heap. */
return result;
}
/**
* Dequeues and returns the minimum element of the Fibonacci heap. If the
* heap is empty, this throws a NoSuchElementException.
*
* @return The smallest element of the Fibonacci heap.
* @throws NoSuchElementException If the heap is empty.
*/
public Entry<T> dequeueMin() {
/* Check for whether we're empty. */
if (isEmpty())
throw new NoSuchElementException("Heap is empty.");
/* Otherwise, we're about to lose an element, so decrement the number of
* entries in this heap.
*/
--mSize;
/* Grab the minimum element so we know what to return. */
Entry<T> minElem = mMin;
/* Now, we need to get rid of this element from the list of roots. There
* are two cases to consider. First, if this is the only element in the
* list of roots, we set the list of roots to be null by clearing mMin.
* Otherwise, if it's not null, then we write the elements next to the
* min element around the min element to remove it, then arbitrarily
* reassign the min.
*/
if (mMin.mNext == mMin) { // Case one
mMin = null;
}
else { // Case two
mMin.mPrev.mNext = mMin.mNext;
mMin.mNext.mPrev = mMin.mPrev;
mMin = mMin.mNext; // Arbitrary element of the root list.
}
/* Next, clear the parent fields of all of the min element's children,
* since they're about to become roots. Because the elements are
* stored in a circular list, the traversal is a bit complex.
*/
if (minElem.mChild != null) {
/* Keep track of the first visited node. */
Entry<?> curr = minElem.mChild;
do {
curr.mParent = null;
/* Walk to the next node, then stop if this is the node we
* started at.
*/
curr = curr.mNext;
} while (curr != minElem.mChild);
}
/* Next, splice the children of the root node into the topmost list,
* then set mMin to point somewhere in that list.
*/
mMin = mergeLists(mMin, minElem.mChild);
/* If there are no entries left, we're done. */
if (mMin == null) return minElem;
/* Next, we need to coalsce all of the roots so that there is only one
* tree of each degree. To track trees of each size, we allocate an
* ArrayList where the entry at position i is either null or the
* unique tree of degree i.
*/
List<Entry<T>> treeTable = new ArrayList<Entry<T>>();
/* We need to traverse the entire list, but since we're going to be
* messing around with it we have to be careful not to break our
* traversal order mid-stream. One major challenge is how to detect
* whether we're visiting the same node twice. To do this, we'll
* spent a bit of overhead adding all of the nodes to a list, and
* then will visit each element of this list in order.
*/
List<Entry<T>> toVisit = new ArrayList<Entry<T>>();
/* To add everything, we'll iterate across the elements until we
* find the first element twice. We check this by looping while the
* list is empty or while the current element isn't the first element
* of that list.
*/
for (Entry<T> curr = mMin; toVisit.isEmpty() || toVisit.get(0) != curr; curr = curr.mNext)
toVisit.add(curr);
/* Traverse this list and perform the appropriate unioning steps. */
for (Entry<T> curr: toVisit) {
/* Keep merging until a match arises. */
while (true) {
/* Ensure that the list is long enough to hold an element of this
* degree.
*/
while (curr.mDegree >= treeTable.size())
treeTable.add(null);
/* If nothing's here, we're can record that this tree has this size
* and are done processing.
*/
if (treeTable.get(curr.mDegree) == null) {
treeTable.set(curr.mDegree, curr);
break;
}
/* Otherwise, merge with what's there. */
Entry<T> other = treeTable.get(curr.mDegree);
treeTable.set(curr.mDegree, null); // Clear the slot
/* Determine which of the two trees has the smaller root, storing
* the two tree accordingly.
*/
Entry<T> min = (other.mPriority < curr.mPriority)? other : curr;
Entry<T> max = (other.mPriority < curr.mPriority)? curr : other;
/* Break max out of the root list, then merge it into min's child
* list.
*/
max.mNext.mPrev = max.mPrev;
max.mPrev.mNext = max.mNext;
/* Make it a singleton so that we can merge it. */
max.mNext = max.mPrev = max;
min.mChild = mergeLists(min.mChild, max);
/* Reparent max appropriately. */
max.mParent = min;
/* Clear max's mark, since it can now lose another child. */
max.mIsMarked = false;
/* Increase min's degree; it now has another child. */
++min.mDegree;
/* Continue merging this tree. */
curr = min;
}
/* Update the global min based on this node. Note that we compare
* for <= instead of < here. That's because if we just did a
* reparent operation that merged two different trees of equal
* priority, we need to make sure that the min pointer points to
* the root-level one.
*/
if (curr.mPriority <= mMin.mPriority) mMin = curr;
}
return minElem;
}
/**
* Decreases the key of the specified element to the new priority. If the
* new priority is greater than the old priority, this function throws an
* IllegalArgumentException. The new priority must be a finite double,
* so you cannot set the priority to be NaN, or +/- infinity. Doing
* so also throws an IllegalArgumentException.
*
* It is assumed that the entry belongs in this heap. For efficiency
* reasons, this is not checked at runtime.
*
* @param entry The element whose priority should be decreased.
* @param newPriority The new priority to associate with this entry.
* @throws IllegalArgumentException If the new priority exceeds the old
* priority, or if the argument is not a finite double.
*/
public void decreaseKey(Entry<T> entry, double newPriority) {
checkPriority(newPriority);
if (newPriority > entry.mPriority)
throw new IllegalArgumentException("New priority exceeds old.");
/* Forward this to a helper function. */
decreaseKeyUnchecked(entry, newPriority);
}
/**
* Deletes this Entry from the Fibonacci heap that contains it.
*
* It is assumed that the entry belongs in this heap. For efficiency
* reasons, this is not checked at runtime.
*
* @param entry The entry to delete.
*/
public void delete(Entry<T> entry) {
/* Use decreaseKey to drop the entry's key to -infinity. This will
* guarantee that the node is cut and set to the global minimum.
*/
decreaseKeyUnchecked(entry, Double.NEGATIVE_INFINITY);
/* Call dequeueMin to remove it. */
dequeueMin();
}
/**
* Utility function which, given a user-specified priority, checks whether
* it's a valid double and throws an IllegalArgumentException otherwise.
*
* @param priority The user's specified priority.
* @throws IllegalArgumentException If it is not valid.
*/
private void checkPriority(double priority) {
if (Double.isNaN(priority))
throw new IllegalArgumentException(priority + " is invalid.");
}
/**
* Utility function which, given two pointers into disjoint circularly-
* linked lists, merges the two lists together into one circularly-linked
* list in O(1) time. Because the lists may be empty, the return value
* is the only pointer that's guaranteed to be to an element of the
* resulting list.
*
* This function assumes that one and two are the minimum elements of the
* lists they are in, and returns a pointer to whichever is smaller. If
* this condition does not hold, the return value is some arbitrary pointer
* into the doubly-linked list.
*
* @param one A pointer into one of the two linked lists.
* @param two A pointer into the other of the two linked lists.
* @return A pointer to the smallest element of the resulting list.
*/
private static <T> Entry<T> mergeLists(Entry<T> one, Entry<T> two) {
/* There are four cases depending on whether the lists are null or not.
* We consider each separately.
*/
if (one == null && two == null) { // Both null, resulting list is null.
return null;
}
else if (one != null && two == null) { // Two is null, result is one.
return one;
}
else if (one == null && two != null) { // One is null, result is two.
return two;
}
else { // Both non-null; actually do the splice.
/* This is actually not as easy as it seems. The idea is that we'll
* have two lists that look like this:
*
* +----+ +----+ +----+
* | |--N->|one |--N->| |
* | |<-P--| |<-P--| |
* +----+ +----+ +----+
*
*
* +----+ +----+ +----+
* | |--N->|two |--N->| |
* | |<-P--| |<-P--| |
* +----+ +----+ +----+
*
* And we want to relink everything to get
*
* +----+ +----+ +----+---+
* | |--N->|one | | | |
* | |<-P--| | | |<+ |
* +----+ +----+<-\ +----+ | |
* \ P | |
* N \ N |
* +----+ +----+ \->+----+ | |
* | |--N->|two | | | | |
* | |<-P--| | | | | P
* +----+ +----+ +----+ | |
* ^ | | |
* | +-------------+ |
* +-----------------+
*
*/
Entry<T> oneNext = one.mNext; // Cache this since we're about to overwrite it.
one.mNext = two.mNext;
one.mNext.mPrev = one;
two.mNext = oneNext;
two.mNext.mPrev = two;
/* Return a pointer to whichever's smaller. */
return one.mPriority < two.mPriority? one : two;
}
}
/**
* Decreases the key of a node in the tree without doing any checking to ensure
* that the new priority is valid.
*
* @param entry The node whose key should be decreased.
* @param priority The node's new priority.
*/
private void decreaseKeyUnchecked(Entry<T> entry, double priority) {
/* First, change the node's priority. */
entry.mPriority = priority;
/* If the node no longer has a higher priority than its parent, cut it.
* Note that this also means that if we try to run a delete operation
* that decreases the key to -infinity, it's guaranteed to cut the node
* from its parent.
*/
if (entry.mParent != null && entry.mPriority <= entry.mParent.mPriority)
cutNode(entry);
/* If our new value is the new min, mark it as such. Note that if we
* ended up decreasing the key in a way that ties the current minimum
* priority, this will change the min accordingly.
*/
if (entry.mPriority <= mMin.mPriority)
mMin = entry;
}
/**
* Cuts a node from its parent. If the parent was already marked, recursively
* cuts that node from its parent as well.
*
* @param entry The node to cut from its parent.
*/
private void cutNode(Entry<T> entry) {
/* Begin by clearing the node's mark, since we just cut it. */
entry.mIsMarked = false;
/* Base case: If the node has no parent, we're done. */
if (entry.mParent == null) return;
/* Rewire the node's siblings around it, if it has any siblings. */
if (entry.mNext != entry) { // Has siblings
entry.mNext.mPrev = entry.mPrev;
entry.mPrev.mNext = entry.mNext;
}
/* If the node is the one identified by its parent as its child,
* we need to rewrite that pointer to point to some arbitrary other
* child.
*/
if (entry.mParent.mChild == entry) {
/* If there are any other children, pick one of them arbitrarily. */
if (entry.mNext != entry) {
entry.mParent.mChild = entry.mNext;
}
/* Otherwise, there aren't any children left and we should clear the
* pointer and drop the node's degree.
*/
else {
entry.mParent.mChild = null;
}
}
/* Decrease the degree of the parent, since it just lost a child. */
--entry.mParent.mDegree;
/* Splice this tree into the root list by converting it to a singleton
* and invoking the merge subroutine.
*/
entry.mPrev = entry.mNext = entry;
mMin = mergeLists(mMin, entry);
/* Mark the parent and recursively cut it if it's already been
* marked.
*/
if (entry.mParent.mIsMarked)
cutNode(entry.mParent);
else
entry.mParent.mIsMarked = true;
/* Clear the relocated node's parent; it's now a root. */
entry.mParent = null;
}
public static void main(String[] args) {
FibonacciHeap<Integer> node = new FibonacciHeap<Integer>();
if(node.isEmpty()) System.out.println("Empty");
else System.out.println("Not empty");
node.enqueue(10,1);
System.out.println((node.min()).getValue());
node.enqueue(5,1);
System.out.println((node.min()).getValue());
node.enqueue(7,1);
System.out.println((node.min()).getValue());
}
}
如果您查看 mergeLists 方法，它使用此行 return mMin:
/* Return a pointer to whichever's smaller. */
return one.mPriority < two.mPriority? one : two;
因此，当您将 7 排入队列时，因为它与 5 具有相同的优先级，所以当您调用 min() 时，它 return 是 7。