算法导论第十九章 斐波那契堆

#ifndef _FIBONACCI_HEAP_H_
#define _FIBONACCI_HEAP_H_

template<typename Data, typename Key> 
class FibHeapNode
{
public:
    template<typename D, typename K> friend class FibHeap;
    FibHeapNode() {}
    FibHeapNode( Data d, Key k): 
        myKey( k ),
        myData( d ),
        degree( 0 ),
        marked( false ),
        child( NULL )
    {
        prev = next = this; //doubly linked circular list
    }

    Key key() const
    {
        return myKey;
    }

    Data data() const 
    {
        return myData;
    }

public:
    bool isSingle() const 
    {
        return ( this == this->next );
    }
    
    //插入一个节点或节点链表
    void Insert( FibHeapNode<Data, Key> *other ) 
    {
        if ( !other )
            return;
        //for example: given 1->2->3->1, insert a->b->c->a after node 3;
        //result: 1->2->3->a->b->c->1
        this->next->prev = other->prev;
        other->prev->next = this->next;
        
        this->next = other;
        other->prev = this;
    }
    
    //删除当前节点
    void RemoveNode()
    {
        this->prev->next = this->next;
        this->next->prev = this->prev;
        this->next = this->prev = this;
    }

    //连接其他节点到当前节点
    void addChild( FibHeapNode<Data, Key> *other )
    {
        if ( !child )
            child = other;
        else 
            child->Insert( other );
        //更新相应的信息
        other->parent = this;
        other->marked = false;
        degree ++;
    }
    
    //删除孩子节点
    void removeChild( FibHeapNode<Data, Key> *other )
    {
        if ( other->parent != this )
            throw string ( "Trying to remove a child from a non-parent!");
        //只有一个节点
        if ( other->isSingle() ) {
            if ( child != other )
                throw string ("Trying to remove a non-child");
            child = NULL;
        }
        else {
            if ( child == other ) {
                child = other->next;
            }
            other->RemoveNode();
        }
        //更新
        other->parent = NULL;
        other->marked = false;
        degree --;
    }

    //<<操作符重载
    friend ostream& operator<< ( ostream& out, const FibHeapNode& n)
    {
        return ( out << n.myData << ";" << n.myKey );
    }

    //打印树
    void printTree( ostream& out ) const
    {
        out << myData << ":" << myKey << ":" << degree << ":" << marked;
        if ( child ) {
            out << "(";
            const FibHeapNode<Data, Key> *n = child;
            do {
                if ( n== this )
                    throw string ( "Illegal pointer - node is child of itself");
                n->printTree( out );
                out << " ";
                n = n->next;
            }while ( n != child );
            out << ")";
        }
    }

    void printAll( ostream& out) const
    {
        const FibHeapNode<Data, Key> *n = this;
        do {
            n->printTree( out );
            out << " ";
            n = n->next;
        }while ( n != this );
        out << endl;
    }

private:
    Key        myKey;
    Data    myData;

    unsigned int    degree; //节点的孩子节点数
    bool            marked;    //标识一个节点的孩子节点是否被删除过，用于decreaseKey 操作

    FibHeapNode<Data, Key>    *prev;    //双循环链表的上一个节点
    FibHeapNode<Data, Key>    *next;    //双循环链表的下一个节点

    FibHeapNode<Data, Key>    *child;    //孩子链表中的第
    一个节点
    FibHeapNode<Data, Key>    *parent;//父节点
};

template<typename Data, typename Key>
class FibHeap
{
public:
    FibHeap() {}
    FibHeap(): rootWithMinKey( NULL ), nCount( 0 ), maxDegree( 0 ) { }

    ~FibHeap(){

    }

    bool empty() const 
    {
        return nCount == 0;
    }

    pNode minimum() const
    {
        if ( !rootWithMinKey )
            throw string("no minimum element");
        return rootWithMinKey;
    }

    void printRoots( ostream &out ) const 
    {
        out << "maxDegree=" << maxDegree << "  count=" << count << "  roots=";
        if ( rootWithMinKey )
            rootWithMinKey->printAll( out );
        else
            out << endl;
    }

    void merge ( const FibHeap& other )  // Fibonacci-Heap-Union
    {
        rootWithMinKey->Insert( other.rootWithMinKey );
        if ( !rootWithMinKey || ( other.rootWithMinKey && other.rootWithMinKey->key() < rootWithMinKey->key() ) )
            this->rootWithMinKey = other.rootWithMinKey;
        nCount += other.nCount;
    }

    pNode insertHeap( Data d, Key k )
    {
        nCount ++;
        return insertNode( new FibHeapNode<Data, Key>(d, k));
    }
    
    void removeMinimum()    // Fibonacci-Heap-Extract-Min, CONSOLIDATE
    {
        if ( !rootWithMinKey )
            throw string( "trying to remove from an empty heap" );

        /// Phase 1: Make all the removed root's children new roots:
        // Make all children of root new roots:
        if ( rootWithMinKey->child )
        {
            pNode c = rootWithMinKey->child;
            do
            {
                c->parent = NULL;
                c = c->next;
            }
            while ( c != rootWithMinKey->child );
            rootWithMinKey->child = NULL; // removed all children
            rootWithMinKey->Insert( c );
        }

        /// Phase 2-a: handle the case where we delete the last myKey:
        if ( rootWithMinKey->next == rootWithMinKey )
        {
            if ( count != 0 )
                throw string ( "Internal error: should have 0 keys" );
            rootWithMinKey = NULL;
            return;
        }

        /// Phase 2: merge roots with the same degree:
        vector<pNode> degreeRoots ( maxDegree + 1 ); // make room for a new degree
        fill ( degreeRoots.begin(), degreeRoots.end(), ( pNode )NULL );
        maxDegree = 0;
        pNode currentPointer = rootWithMinKey->next;
        unsigned int currentDegree;
        do
        {
            currentDegree = currentPointer->degree;

            pNode current = currentPointer;
            currentPointer = currentPointer->next;
            while ( degreeRoots[currentDegree] ) // merge the two roots with the same degree:
            {
                pNode other = degreeRoots[currentDegree]; // another root with the same degree
                if ( current->key() > other->key() )
                    swap( other, current );
                // now current->key() <= other->key() - make other a child of current:
                other->RemoveNode(); // remove from list of roots
                current->addChild( other );
                
                degreeRoots[currentDegree] = NULL;
                currentDegree++;
                if ( currentDegree >= degreeRoots.size() )
                    degreeRoots.push_back( ( pNode )NULL );
            }
            // keep the current root as the first of its degree in the degrees array:
            degreeRoots[currentDegree] = current;
        }
        while ( currentPointer != rootWithMinKey );

        /// Phase 3: remove the current root, and calcualte the new rootWithMinKey:
        delete rootWithMinKey;
        rootWithMinKey = NULL;

        unsigned int newMaxDegree = 0;
        for ( unsigned int d = 0; d < degreeRoots.size(); ++d )
        {
            if ( degreeRoots[d] )
            {
                degreeRoots[d]->next = degreeRoots[d]->prev = degreeRoots[d];
                insertNode( degreeRoots[d] );
                if ( d > newMaxDegree )
                    newMaxDegree = d;
            }
        }
        maxDegree = newMaxDegree;
    }
    
    void decreaseKey( pNode node, Key newKey )
    {
        if ( newKey >= node->myKey )
            throw string( "Trying to decrease key to a greater key" );

        // Update the key and possibly the min key:
        node->myKey = newKey;

        // Check if the new key violates the heap invariant:
        pNode parent = node->parent;
        if ( !parent ) // root node - just make sure the minimum is correct
        {
            if ( newKey < rootWithMinKey->key() )
                rootWithMinKey = node;
            return; // heap invariant not violated - nothing more to do
        }
        else if ( parent->key() <= newKey )
        {
            return; // heap invariant not violated - nothing more to do
        }

        for( ;; )
        {
            parent->removeChild( node );
            insertNode( node );

            if ( !parent->parent ) // parent is a root - nothing more to do
            {
                break;
            }
            else if ( !parent->marked )    // parent is not a root and is not marked - just mark it
            {
                parent->marked = true;
                break;
            }
            else
            {
                node = parent;
                parent = parent->parent;
                continue;
            }
        }
    }

    void remove( pNode node, Key minusInfinity )
    {
        if ( minusInfinity >= minimum()->key() )
            throw string( "2nd argument to remove must be a key that is smaller than all other keys" );
        decreaseKey( node, minusInfinity );
        removeMinimum();
    }



protected:
    pNode insertNode ( pNode newNode )
    {
        if ( !rootWithMinKey )
            rootWithMinKey = newNode;
        else {
            rootWithMinKey->Insert( newNode );
            if ( newNode->key() < rootWithMinKey->key() )
                rootWithMinKey = newNode;
        }
        return newNode;
    }


private:
    typedef FibHeapNode<Data, Key>* pNode;

    pNode rootWithMinKey;
    unsigned int nCount;
    unsigned int maxDegree;
};


#endif//_FIBONACCI_HEAP_H_