public class PairingHeap {
private HeapNode minNode;
private HeapNode [] nodes;
public PairingHeap(int numOfNodes) {
minNode = null;
nodes = new HeapNode[numOfNodes+1];
}
public void insert(int item, int priority) {
HeapNode node = new HeapNode(item, priority, null, null);
minNode = merge(minNode, node);
nodes[item] = node;
}
private HeapNode merge(HeapNode a, HeapNode b) {
if(a == null) {
return b;
}
if(b == null) {
return a;
}
if(a.key < b.key) {
a.addChild(b);
return a;
}
else {
b.addChild(a);
return b;
}
}
public void decreaseKey(int item, int newPriority) {
HeapNode curr = nodes[item];
if(curr == null) {
System.out.println("This Node doesn't exist!");
return;
}
curr.key = newPriority;
if(curr.parent != null && curr.key < curr.parent.key) {
if(curr.parent.leftChild != null && curr.parent.leftChild.item == curr.item) {
//Case Decreased Node is LeftChild of Parent
curr.parent.leftChild = curr.parent.leftChild.rightSibling;
}else {
//Case Decrease Node is some Right Sibling
HeapNode temp = curr.parent.leftChild;
while(temp != null && temp.rightSibling != null && temp.rightSibling.item != curr.item){
temp = temp.rightSibling;
}
if(temp != null) {
temp.rightSibling = temp.rightSibling.rightSibling;
}
}
minNode = merge(minNode, curr);
return;
}
// Case Decreases Node is root
minNode = mergeTwoPairNodes(minNode);
}
public int findMin() {
return minNode == null ? -1 : minNode.item;
}
public int deleteMin(){
HeapNode result = minNode;
minNode = mergeTwoPairNodes(minNode.leftChild);
if(minNode != null) minNode.parent = null;
return result == null ? -1 : result.item;
}
private HeapNode mergeTwoPairNodes(HeapNode node) {
if(node == null || node.rightSibling == null) {
return node;
}else {
HeapNode a = node;
HeapNode b = node.rightSibling;
HeapNode newNode = node.rightSibling.rightSibling;
a.rightSibling = null;
b.rightSibling = null;
return merge(merge(a, b), mergeTwoPairNodes(newNode));
}
}
}
class HeapNode{
public int item;
public int key;
public HeapNode leftChild;
public HeapNode rightSibling;
public HeapNode parent;
public HeapNode(int item, int key, HeapNode leftChild, HeapNode parent) {
this.item = item;
this.key = key;
this.leftChild = leftChild;
this.rightSibling = null;
this.parent = parent;
}
public void addChild(HeapNode node) {
if(leftChild == null) {
leftChild = node;
node.parent = this;
return;
}
if(leftChild.rightSibling == null) {
leftChild.rightSibling = node;
node.parent = this;
return;
}
HeapNode temp = leftChild;
while(temp.rightSibling != null) {
temp = temp.rightSibling;
}
if(temp != null) {
temp.rightSibling = node;
node.parent = this;
}
}
public String toString() {
return "(Item: " + item + ", Key: " + key + ")";
}
}