Đại học Lê Quý Đôn - 236 Hoàng Quốc Việt - Hà Nội

Chia sẻ kiến thức mọi mặt của các lớp cao học CNTT, Học viện Kỹ thuật Quân sự




Chào mừng đã đến với forum khmt.123.st
  • Bạn chưa đăng kí (hoặc chưa đăng nhập) nên quyền lợi của bạn sẽ bị hạn chế. Việc đăng kí làm thành viên hoàn toàn miễn phí, sau khi đăngkí bạn có thể post bài, tham gia thảo luận , nhìn thấy link ở những box hạn chế ... và rất nhiều quyền lợi khác. Thủ tục đăng kí rất nhanh chóng và đơn giản, hãy Đăng kí làm thành viên !
  • Nếu bạn quên mật khẩu, xin nhấn vào đây !
  • Nếu bạn gặp trục trặc trong vấn đề đăng kí hoặc không thể đăng nhập, hãy liên hệ với chúng tôi.




  • Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down  Thông điệp [Trang 1 trong tổng số 1 trang]

    1 pairing heap on Mon Apr 23, 2012 7:26 pm

    huongngoc


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    các anh chị ơi. giúp em với. em đang tìm hiểu về pairing heap. anh chị nào có tài liệu về pairing heap không. up lên cho em với. em tìm trong thư viện chuẩn nhưng không thấy ạ

    Ban QT:
    Code đây
    code - Nháy vào đây để hiện:
    Code:

    PairingHeap.cpp - Implementation FOR pairing heap
       
        #include "PairingHeap.h"
            #include "dsexceptions.h"
            /**
            * Construct the pairing heap.
            */
            template <class Comparable>
            PairingHeap<Comparable>::PairingHeap( )
            {
                root = NULL;
            }
            /**
            * Copy constructor
            */
            template <class Comparable>
            PairingHeap<Comparable>::PairingHeap( const PairingHeap<Comparable> & rhs )
            {
                root = NULL;
                *this = rhs;
            }
            /**
            * Destroy the leftist heap.
            */
            template <class Comparable>
            PairingHeap<Comparable>::~PairingHeap( )
            {
                makeEmpty( );
            }
            /**
            * Insert item x into the priority queue, maintaining heap order.
            * Return a pointer to the node containing the new item.
            */
            template <class Comparable>
            PairNode<Comparable> *
            PairingHeap<Comparable>::insert( const Comparable & x )
            {
                PairNode<Comparable> *newNode = new PairNode<Comparable>( x );

                if( root == NULL )
                    root = newNode;
                ELSE
                    compareAndLink( root, newNode );
                return newNode;
            }
            /**
            * Find the smallest item in the priority queue.
            * Return the smallest item, or throw Underflow if empty.
            */
            template <class Comparable>
            const Comparable & PairingHeap<Comparable>::findMin( ) const
            {
                if( isEmpty( ) )
                    throw Underflow( );
                return root->element;
            }
            /**
            * Remove the smallest item from the priority queue.
            * Throws Underflow if empty.
            */
            template <class Comparable>
            void PairingHeap<Comparable>::deleteMin( )
            {
                if( isEmpty( ) )
                    throw Underflow( );

                PairNode<Comparable> *oldRoot = root;

                if( root->leftChild == NULL )
                    root = NULL;
                ELSE
                    root = combineSiblings( root->leftChild );
                delete oldRoot;
            }
            /**
            * Remove the smallest item from the priority queue.
            * Pass back the smallest item, or throw Underflow if empty.
            */
            template <class Comparable>
            void PairingHeap<Comparable>::deleteMin( Comparable & minItem )
            {
                minItem = findMin( );
                deleteMin( );
            }
            /**
            * Test if the priority queue is logically empty.
            * Returns true if empty, false otherwise.
            */
            template <class Comparable>
            bool PairingHeap<Comparable>::isEmpty( ) const
            {
                return root == NULL;
            }
            /**
            * Test if the priority queue is logically full.
            * Returns false in this implementation.
            */
            template <class Comparable>
            bool PairingHeap<Comparable>::isFull( ) const
            {
                return false;
            }
            /**
            * Make the priority queue logically empty.
            */
            template <class Comparable>
            void PairingHeap<Comparable>::makeEmpty( )
            {
                reclaimMemory( root );
                root = NULL;
            }
            /**
            * Deep copy.
            */
            template <class Comparable>
            const PairingHeap<Comparable> &
            PairingHeap<Comparable>::operator=( const PairingHeap<Comparable> & rhs )
            {
                if( this != &rhs )
                {
                    makeEmpty( );
                    root = clone( rhs.root );
                }
                return *this;
            }
            /**
            * Internal method to make the tree empty.
            * WARNING: This is prone to running out of stack space.
            */
            template <class Comparable>
            void PairingHeap<Comparable>::reclaimMemory( PairNode<Comparable> * t ) const
            {
                if( t != NULL )
                {
                    reclaimMemory( t->leftChild );
                    reclaimMemory( t->nextSibling );
                    delete t;
                }
            }
            /**
            * Change the value of the item stored in the pairing heap.
            * Does nothing if newVal is larger than currently stored value.
            * p points to a node returned by insert.
            * newVal is the new value, which must be smaller
            *    than the currently stored value.
            */
            template <class Comparable>
            void PairingHeap<Comparable>::decreaseKey( PairNode<Comparable> *p,
                                                      const Comparable & newVal )
            {
                if( p->element < newVal )
                    return;    // newVal cannot be bigger
                p->element = newVal;
                if( p != root )
                {
                    if( p->nextSibling != NULL )
                        p->nextSibling->prev = p->prev;
                    if( p->prev->leftChild == p )
                        p->prev->leftChild = p->nextSibling;
                    ELSE
                        p->prev->nextSibling = p->nextSibling;
                    p->nextSibling = NULL;
                    compareAndLink( root, p );
                }
            }
            /**
            * Internal method that is the basic operation to maintain order.
            * Links first and second together to satisfy heap order.
            * first is root of tree 1, which may not be NULL.
            *    first->nextSibling MUST be NULL on entry.
            * second is root of tree 2, which may be NULL.
            * first becomes the result of the tree merge.
            */
            template <class Comparable>
            void PairingHeap<Comparable>::
            compareAndLink( PairNode<Comparable> * & first,
                            PairNode<Comparable> *second ) const
            {
                if( second == NULL )
                    return;

                if( second->element < first->element )
                {
                    // Attach first as leftmost child of second
                    second->prev = first->prev;
                    first->prev = second;
                    first->nextSibling = second->leftChild;
                    if( first->nextSibling != NULL )
                        first->nextSibling->prev = first;
                    second->leftChild = first;
                    first = second;
                }
                ELSE
                {
                    // Attach second as leftmost child of first
                    second->prev = first;
                    first->nextSibling = second->nextSibling;
                    if( first->nextSibling != NULL )
                        first->nextSibling->prev = first;
                    second->nextSibling = first->leftChild;
                    if( second->nextSibling != NULL )
                        second->nextSibling->prev = second;
                    first->leftChild = second;
                }
            }
            /**
            * Internal method that implements two-pass merging.
            * firstSibling the root of the conglomerate;
            *    assumed not NULL.
            */
            template <class Comparable>
            PairNode<Comparable> *
            PairingHeap<Comparable>::
            combineSiblings( PairNode<Comparable> *firstSibling ) const
            {
                if( firstSibling->nextSibling == NULL )
                    return firstSibling;
                    // Allocate the array
                static vector<PairNode<Comparable> *> treeArray( 5 );
                    // Store the subtrees in an array
                int numSiblings = 0;
                FOR( ; firstSibling != NULL; numSiblings++ )
                {
                    if( numSiblings == treeArray.size( ) )
                        treeArray.resize( numSiblings * 2 );
                    treeArray[ numSiblings ] = firstSibling;
                    firstSibling->prev->nextSibling = NULL;  // break links
                    firstSibling = firstSibling->nextSibling;
                }
                if( numSiblings == treeArray.size( ) )
                    treeArray.resize( numSiblings + 1 );
                treeArray[ numSiblings ] = NULL;

                    // Combine subtrees two at a time, going left to right
                int i = 0;
                FOR( ; i + 1 < numSiblings; i += 2 )
                    compareAndLink( treeArray[ i ], treeArray[ i + 1 ] );
                int j = i - 2;
                    // j has the result of last compareAndLink.
                    // If an odd number of trees, get the last one.
                if( j == numSiblings - 3 )
                    compareAndLink( treeArray[ j ], treeArray[ j + 2 ] );

                    // Now go right to left, merging last tree with
                    // next to last. The result becomes the new last.
                FOR( ; j >= 2; j -= 2 )
                    compareAndLink( treeArray[ j - 2 ], treeArray[ j ] );
                return treeArray[ 0 ];
            }

            /**
            * Internal method to clone subtree.
            * WARNING: This is prone to running out of stack space.
            */
            template <class Comparable>
            PairNode<Comparable> *
            PairingHeap<Comparable>::clone( PairNode<Comparable> * t ) const
            {
                if( t == NULL )
                    return NULL;
                ELSE
                {
                    PairNode<Comparable> *p = new PairNode<Comparable>( t->element );
                    if( ( p->leftChild = clone( t->leftChild ) ) != NULL )
                        p->leftChild->prev = p;
                    if( ( p->nextSibling = clone( t->nextSibling ) ) != NULL )
                        p->nextSibling->prev = p;
                    return p;
                }
            }

    2 Re: pairing heap on Tue Apr 24, 2012 6:16 am

    huongngoc


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    hihi. em cám ơn anh nha

    Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang  Thông điệp [Trang 1 trong tổng số 1 trang]

    Permissions in this forum:
    Bạn không có quyền trả lời bài viết

     

    Ghi rõ nguồn khi copy các bài viết từ Website này.
    Bản quyền thuộc Khoa học Máy tính. Số lượt truy cập tính đến hiện tại:Website counter
    Modified skin by Nguyễn Anh Cường. Developed by Members of http://khmt.123.st

    Free forum | © PunBB | Free forum support | Liên hệ | Report an abuse | Sosblogs.com