Code:
#include iostream
#include cstdlib
#include vector
using namespace std;
/*
* Node Class Declaration
*/
class PairNode
{
public:
int element;
PairNode *leftChild;
PairNode *nextSibling;
PairNode *prev;
PairNode(int element)
{
this->element = element;
leftChild = NULL;
nextSibling = NULL;
prev = NULL;
}
};
/*
* Class Declaration
*/
class PairingHeap
{
private:
PairNode *root;
void reclaimMemory(PairNode *t);
void compareAndLink(PairNode * &first, PairNode *second);
PairNode *combineSiblings(PairNode *firstSibling);
PairNode *clone(PairNode *t);
public:
PairingHeap();
PairingHeap(PairingHeap &rhs);
~PairingHeap();
bool isEmpty();
bool isFull();
int &findMin();
PairNode *Insert(int &x);
void deleteMin();
void deleteMin(int &minItem);
void makeEmpty();
void decreaseKey(PairNode *p, int &newVal );
PairingHeap &operator=(PairingHeap &rhs);
};
PairingHeap::PairingHeap()
{
root = NULL;
}
PairingHeap::PairingHeap(PairingHeap & rhs)
{
root = NULL;
*this = rhs;
}
/*
* Destroy the leftist heap.
*/
PairingHeap::~PairingHeap()
{
makeEmpty();
}
/*
* Insert item x into the priority queue, maintaining heap order.
* Return a pointer to the node containing the new item.
*/
PairNode *PairingHeap::Insert(int &x)
{
PairNode *newNode = new PairNode(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.
*/
int &PairingHeap::findMin()
{
return root->element;
}
/*
* Remove the smallest item from the priority queue.
* Throws Underflow if empty.
*/
void PairingHeap::deleteMin()
{
PairNode *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.
*/
void PairingHeap::deleteMin(int &minItem)
{
if (isEmpty())
{
cout<<"The Heap is Empty"<
return;
}
minItem = findMin();
deleteMin();
cout<<"Minimum Element: "<
}
/*
* Test if the priority queue is logically empty.
* Returns true if empty, false otherwise.
*/
bool PairingHeap::isEmpty()
{
return root == NULL;
}
/*
* Test if the priority queue is logically full.
* Returns false in this implementation.
*/
bool PairingHeap::isFull()
{
return false;
}
/*
* Make the priority queue logically empty.
*/
void PairingHeap::makeEmpty()
{
reclaimMemory(root);
root = NULL;
}
/*
* Deep copy.
*/
PairingHeap &PairingHeap::operator=(PairingHeap & rhs)
{
if (this != &rhs)
{
makeEmpty( );
root = clone(rhs.root);
}
return *this;
}
/*
* Internal method to make the tree empty.
*/
void PairingHeap::reclaimMemory(PairNode * t)
{
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.
*/
void PairingHeap::decreaseKey(PairNode *p, int &newVal)
{
if (p->element < newVal)
return;
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.
*/
void PairingHeap::compareAndLink(PairNode * &first, PairNode *second)
{
if (second == NULL)
return;
if (second->element < first->element)
{
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
{
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.
*/
PairNode *PairingHeap::combineSiblings(PairNode *firstSibling)
{
if (firstSibling->nextSibling == NULL)
return firstSibling;
static vector
int numSiblings = 0;
for (; firstSibling != NULL; numSiblings++)
{
if (numSiblings == treeArray.size())
treeArray.resize(numSiblings * 2);
treeArray[numSiblings] = firstSibling;
firstSibling->prev->nextSibling = NULL;
firstSibling = firstSibling->nextSibling;
}
if (numSiblings == treeArray.size())
treeArray.resize(numSiblings + 1);
treeArray[numSiblings] = NULL;
int i = 0;
for (; i + 1 < numSiblings; i += 2)
compareAndLink(treeArray[i], treeArray[i + 1]);
int j = i - 2;
if (j == numSiblings - 3)
compareAndLink (treeArray[j], treeArray[j + 2]);
for (; j >= 2; j -= 2)
compareAndLink(treeArray[j - 2], treeArray[j] );
return treeArray[0];
}
/*
* Internal method to clone subtree.
*/
PairNode *PairingHeap::clone(PairNode * t)
{
if (t == NULL)
return NULL;
else
{
PairNode *p = new PairNode(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;
}
}
/*
* Main Contains Menu
*/
int main()
{
int choice, num, pos;
char ch;
PairingHeap h;
PairNode * pn;
while (1)
{
cout<<"-----------------"<
cout<<"Operations on Pairing Heap"<
cout<<"-----------------"<
cout<<"1.Insert Element and Decrease key"<
cout<<"2.Delete Minimum Element "<
cout<<"3.Quit"<
cout<<"Enter your choice : ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter the number to be inserted : ";
cin>>num;
pn = h.Insert(num);
cout<<"Want to decrease the key:(Y = Yes | N = No) ";
cin>>ch;
if (ch == 'Y')
{
cout<<"Enter new key value: ";
cin>>pos;
h.decreaseKey(pn, pos);
}
break;
case 2:
h.deleteMin(num);
break;
case 3:
exit(1);
default:
cout<<"Wrong choice"<
}
}
return 0;
}
Output:
-----------------
Operations on Pairing Heap
-----------------
1.Insert Element and Decrease key
2.Delete Minimum Element
3.Quit
Enter your choice : 1
Enter the number to be inserted : 100
Want to decrease the key:(Y = Yes | N = No) Y
Enter new key value: 50
-----------------
Operations on Pairing Heap
-----------------
1.Insert Element and Decrease key
2.Delete Minimum Element
3.Quit
Enter your choice : 1
Enter the number to be inserted : 200
Want to decrease the key:(Y = Yes | N = No) N
-----------------
Operations on Pairing Heap
-----------------
1.Insert Element and Decrease key
2.Delete Minimum Element
3.Quit
Enter your choice : 1
Enter the number to be inserted : 300
Want to decrease the key:(Y = Yes | N = No) N
-----------------
Operations on Pairing Heap
-----------------
1.Insert Element and Decrease key
2.Delete Minimum Element
3.Quit
Enter your choice : 1
Enter the number to be inserted : 400
Want to decrease the key:(Y = Yes | N = No) N
-----------------
Operations on Pairing Heap
-----------------
1.Insert Element and Decrease key
2.Delete Minimum Element
3.Quit
Enter your choice : 2
Minimum Element: 50 deleted
-----------------
Operations on Pairing Heap
-----------------
1.Insert Element and Decrease key
2.Delete Minimum Element
3.Quit
Enter your choice : 1
Enter the number to be inserted : 75
Want to decrease the key:(Y = Yes | N = No) N
-----------------
Operations on Pairing Heap
-----------------
1.Insert Element and Decrease key
2.Delete Minimum Element
3.Quit
Enter your choice : 2
Minimum Element: 75 deleted
-----------------
Operations on Pairing Heap
-----------------
1.Insert Element and Decrease key
2.Delete Minimum Element
3.Quit
Enter your choice : 2
Minimum Element: 200 deleted
-----------------
Operations on Pairing Heap
-----------------
1.Insert Element and Decrease key
2.Delete Minimum Element
3.Quit
Enter your choice : 2
Minimum Element: 300 deleted
-----------------
Operations on Pairing Heap
-----------------
1.Insert Element and Decrease key
2.Delete Minimum Element
3.Quit
Enter your choice : 2
Minimum Element: 400 deleted
-----------------
Operations on Pairing Heap
-----------------
1.Insert Element and Decrease key
2.Delete Minimum Element
3.Quit
Enter your choice : 2
The Heap is Empty
-----------------
Operations on Pairing Heap
-----------------
1.Insert Element and Decrease key
2.Delete Minimum Element
3.Quit
Enter your choice : 3
------------------
(program exited with code: 1)
Press return to continue
More C++ Programs:
