1
pairing heap Mon Apr 23, 2012 7:26 pm
huongngoc
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
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;
}
}
