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;
    }
public Entry < T > dequeueMin ( ) { if ( isEmpty ( ) ) throw new NoSuchElementException ( "Heap is empty." ) ; -- mSize ; Entry < T > minElem = mMin ; if ( mMin . mNext == mMin ) { mMin = null ; } else { mMin . mPrev . mNext = mMin . mNext ; mMin . mNext . mPrev = mMin . mPrev ; mMin = mMin . mNext ; } if ( minElem . mChild != null ) { Entry < ? > curr = minElem . mChild ; do { curr . mParent = null ; curr = curr . mNext ; } while ( curr != minElem . mChild ) ; } mMin = mergeLists ( mMin , minElem . mChild ) ; if ( mMin == null ) return minElem ; List < Entry < T > > treeTable = new ArrayList < Entry < T > > ( ) ; List < Entry < T > > toVisit = new ArrayList < Entry < T > > ( ) ; for ( Entry < T > curr = mMin ; toVisit . isEmpty ( ) || toVisit . get ( 0 ) != curr ; curr = curr . mNext ) toVisit . add ( curr ) ; for ( Entry < T > curr : toVisit ) { while ( true ) { while ( curr . mDegree >= treeTable . size ( ) ) treeTable . add ( null ) ; if ( treeTable . get ( curr . mDegree ) == null ) { treeTable . set ( curr . mDegree , curr ) ; break ; } Entry < T > other = treeTable . get ( curr . mDegree ) ; treeTable . set ( curr . mDegree , null ) ; Entry < T > min = ( other . mPriority < curr . mPriority ) ? other : curr ; Entry < T > max = ( other . mPriority < curr . mPriority ) ? curr : other ; max . mNext . mPrev = max . mPrev ; max . mPrev . mNext = max . mNext ; max . mNext = max . mPrev = max ; min . mChild = mergeLists ( min . mChild , max ) ; max . mParent = min ; max . mIsMarked = false ; ++ min . mDegree ; curr = min ; } if ( curr . mPriority <= mMin . mPriority ) mMin = curr ; } return minElem ; }
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 java.util.NoSuchElementException If the heap is empty.