Logo Search packages:      
Sourcecode: libjgrapht-java version File versions  Download package

void org::_3pq::jgrapht::util::FibonacciHeap::consolidate (  )  [inline, protected]

Consolidates the trees in the heap by joining trees of equal degree until there are no more trees of equal degree in the root list.

Running time: O(log n) amortized

Definition at line 445 of file FibonacciHeap.java.

References link(), org::_3pq::jgrapht::util::FibonacciHeap::Node::m_degree, org::_3pq::jgrapht::util::FibonacciHeap::Node::m_key, org::_3pq::jgrapht::util::FibonacciHeap::Node::m_left, m_min, m_n, and org::_3pq::jgrapht::util::FibonacciHeap::Node::m_right.

Referenced by removeMin().

                                   {
        int    arraySize = m_n + 1;
        Node[] array = new Node[ arraySize ];

        // Initialize degree array
        for( int i = 0; i < arraySize; i++ ) {
            array[ i ] = null;
        }

        // Find the number of root nodes.
        int  numRoots = 0;
        Node x = m_min;

        if( x != null ) {
            numRoots++;
            x = x.m_right;

            while( x != m_min ) {
                numRoots++;
                x = x.m_right;
            }
        }

        // For each node in root list do...
        while( numRoots > 0 ) {
            // Access this node's degree..
            int  d    = x.m_degree;
            Node next = x.m_right;

            // ..and see if there's another of the same degree.
            while( array[ d ] != null ) {
                // There is, make one of the nodes a child of the other.
                Node y = array[ d ];

                // Do this based on the key value.
                if( x.m_key > y.m_key ) {
                    Node temp = y;
                    y     = x;
                    x     = temp;
                }

                // Node y disappears from root list.
                link( y, x );

                // We've handled this degree, go to next one.
                array[ d ] = null;
                d++;
            }

            // Save this node for later when we might encounter another
            // of the same degree.
            array[ d ]     = x;

            // Move forward through list.
            x = next;
            numRoots--;
        }

        // Set min to null (effectively losing the root list) and
        // reconstruct the root list from the array entries in array[].
        m_min = null;

        for( int i = 0; i < arraySize; i++ ) {
            if( array[ i ] != null ) {
                // We've got a live one, add it to root list.
                if( m_min != null ) {
                    // First remove node from root list.
                    array[ i ].m_left.m_right     = array[ i ].m_right;
                    array[ i ].m_right.m_left     = array[ i ].m_left;

                    // Now add to root list, again.
                    array[ i ].m_left             = m_min;
                    array[ i ].m_right            = m_min.m_right;
                    m_min.m_right                 = array[ i ];
                    array[ i ].m_right.m_left     = array[ i ];

                    // Check if this is a new min.
                    if( array[ i ].m_key < m_min.m_key ) {
                        m_min = array[ i ];
                    }
                }
                else {
                    m_min = array[ i ];
                }
            }
        }
    }


Generated by  Doxygen 1.6.0   Back to index