Java Program to Implement Pairing Heap

Chapter: Data Structures Last Updated: 13-07-2016 10:03:10 UTC

Program:

            /* ............... START ............... */
                
import java.util.Scanner;

class PairNode {
	int element;
	PairNode leftChild;
	PairNode nextSibling;
	PairNode prev;

	/* Constructor */
	public PairNode(int x) {
		element = x;
		leftChild = null;
		nextSibling = null;
		prev = null;
	}
}

class PairHeap {
	private PairNode root;
	private PairNode[] treeArray = new PairNode[5];

	public PairHeap() {
		root = null;
	}

	public boolean isEmpty() {
		return root == null;
	}

	public void makeEmpty() {
		root = null;
	}

	public PairNode insert(int x) {
		PairNode newNode = new PairNode(x);
		if (root == null)
			root = newNode;
		else
			root = compareAndLink(root, newNode);
		return newNode;
	}

	private PairNode compareAndLink(PairNode first, PairNode second) {
		if (second == null)
			return first;

		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;
			return 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;
			return first;
		}
	}

	private PairNode combineSiblings(PairNode firstSibling) {
		if (firstSibling.nextSibling == null)
			return firstSibling;
		int numSiblings = 0;
		for (; firstSibling != null; numSiblings++) {
			treeArray = doubleIfFull(treeArray, numSiblings);
			treeArray[numSiblings] = firstSibling;
			firstSibling.prev.nextSibling = null;
			firstSibling = firstSibling.nextSibling;
		}
		treeArray = doubleIfFull(treeArray, numSiblings);
		treeArray[numSiblings] = null;
		int i = 0;
		for (; i + 1 < numSiblings; i += 2)
			treeArray[i] = compareAndLink(treeArray[i], treeArray[i + 1]);
		int j = i - 2;
		if (j == numSiblings - 3)
			treeArray[j] = compareAndLink(treeArray[j], treeArray[j + 2]);
		for (; j >= 2; j -= 2)
			treeArray[j - 2] = compareAndLink(treeArray[j - 2], treeArray[j]);
		return treeArray[0];
	}

	private PairNode[] doubleIfFull(PairNode[] array, int index) {
		if (index == array.length) {
			PairNode[] oldArray = array;
			array = new PairNode[index * 2];
			for (int i = 0; i < index; i++)
				array[i] = oldArray[i];
		}
		return array;
	}

	public int deleteMin() {
		if (isEmpty())
			return -1;
		int x = root.element;
		if (root.leftChild == null)
			root = null;
		else
			root = combineSiblings(root.leftChild);
		return x;
	}

	public void inorder() {
		inorder(root);
	}

	private void inorder(PairNode r) {
		if (r != null) {
			inorder(r.leftChild);
			System.out.print(r.element + " ");
			inorder(r.nextSibling);
		}
	}
}

public class JavaPairingHeapExample {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		System.out.println("PairHeap Test\n\n");
		PairHeap ph = new PairHeap();

		char ch;
		do {
			System.out.println("\nPair Heap Operations\n");
			System.out.println("1. insert ");
			System.out.println("2. delete min");
			System.out.println("3. check empty");
			System.out.println("4. clear");

			int choice = scan.nextInt();
			switch (choice) {
			case 1:
				System.out.println("Enter integer element to insert");
				ph.insert(scan.nextInt());
				break;
			case 2:
				ph.deleteMin();
				break;
			case 3:
				System.out.println("Empty status = " + ph.isEmpty());
				break;
			case 4:
				ph.makeEmpty();
				break;
			default:
				System.out.println("Wrong Entry \n ");
				break;
			}
			System.out.print("\nInorder Traversal : ");
			ph.inorder();

			System.out.println("\nDo you want to continue (Type y or n) \n");
			ch = scan.next().charAt(0);
		} while (ch == 'Y' || ch == 'y');
	}
}
                /* ............... END ............... */
        

Output

PairHeap Test



Pair Heap Operations

1. insert 
2. delete min
3. check empty
4. clear
1
Enter integer element to insert
2

Inorder Traversal : 2 
Do you want to continue (Type y or n) 

y

Pair Heap Operations

1. insert 
2. delete min
3. check empty
4. clear

Notes:

  • A pairing heap is a type of heap data structure with relatively simple implementation and excellent practical amortized performance.

Tags

Implement Pairing Heap, Java, Data Structures

Similar Programs Chapter Last Updated
HashMap Implementation In Java Data Structures 07-07-2018
Linked List Implementation In Java Data Structures 09-03-2018
Queue Implementation In Java Data Structures 22-09-2018
Stack Implementation In Java Data Structures 22-09-2018
Binary Search Tree Java Data Structures 11-02-2018
Insertion Sort In Java Data Structures 10-02-2018
Java Stack Example Data Structures 16-10-2017
Java String Array Sort Data Structures 31-03-2017
Java Hashmap Add Key And Value Data Structures 25-03-2017
Java Binary Tree Vertical Sum Data Structures 11-11-2016
Java Binary Tree Boundary Traversal Data Structures 11-11-2016
Java Binary Tree Lowest Common Ancestor (LCA) Data Structures 11-11-2016
Java Binary Tree Maximum Element Data Structures 11-11-2016
Java Three Dimensional Array Data Structures 28-10-2016
Java Infix Expression To Postfix Expression Data Structures 25-10-2016
Java Linked List Add Element First And Last Data Structures 24-10-2016
Java Maximum Element From Vector Data Structures 24-10-2016
Java Binary Search On Vector Data Structures 24-10-2016
Java Get Elements Of LinkedList Data Structures 23-10-2016
Java Linked List Update Element Data Structures 23-10-2016
Java Delete Elements From LinkedList Data Structures 23-10-2016
Java Double Ended Queue Data Structures 09-10-2016
Java Dynamic Queue Using Array Data Structures 26-09-2018
Java Queue Array Based Implementation Data Structures 07-10-2016
Java Sort Short Array Data Structures 25-09-2016
Java Sort Long Array Data Structures 25-09-2016
Java Sort Int Array Data Structures 19-09-2016
Java Sort Float Array Data Structures 19-09-2016
Java Sort Double Array Data Structures 19-09-2016
Java Sort Char Array Data Structures 19-09-2016

1 2 3