Java Program to Implement Pairing Heap

This is a Java Program to implement Pairing Heap. A pairing heap is a type of heap data structure with relatively simple implementation and excellent practical amortized performance. However, it has proven very difficult to determine the precise asymptotic running time of pairing heaps.Pairing heaps are heap ordered multiway trees. This program is based on the implementation by Mark Allen Weiss.

Here is the source code of the Java program to implement Pairing Heap. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. /*
  2.  *  Java Program to Implement Pairing Heap
  3.  */
  4.  
  5. import java.util.Scanner;    
  6. /* Class PairNode */
  7. class PairNode
  8. {
  9.     int element;
  10.     PairNode leftChild;
  11.     PairNode nextSibling;
  12.     PairNode prev;
  13.  
  14.     /* Constructor */
  15.     public PairNode(int x)
  16.     {
  17.         element = x;
  18.         leftChild = null;
  19.         nextSibling = null;
  20.         prev = null;
  21.     }
  22. }
  23.  
  24. /* Class PairHeap */
  25. class PairHeap
  26. {
  27.     private PairNode root; 
  28.     private PairNode [ ] treeArray = new PairNode[ 5 ];
  29.     /* Constructor */
  30.     public PairHeap( )
  31.     {
  32.         root = null;
  33.       }
  34.     /* Check if heap is empty */
  35.     public boolean isEmpty() 
  36.     {
  37.         return root == null;
  38.     }
  39.     /* Make heap logically empty */ 
  40.     public void makeEmpty( )
  41.     {
  42.         root = null;
  43.     }
  44.     /* Function to insert data */
  45.     public PairNode insert(int x)
  46.     {
  47.         PairNode newNode = new PairNode( x );
  48.         if (root == null)
  49.             root = newNode;
  50.         else
  51.             root = compareAndLink(root, newNode);
  52.         return newNode;
  53.     }
  54.     /* Function compareAndLink */
  55.     private PairNode compareAndLink(PairNode first, PairNode second)
  56.     {
  57.         if (second == null)
  58.             return first;
  59.  
  60.         if (second.element < first.element)
  61.         {
  62.             /* Attach first as leftmost child of second */
  63.             second.prev = first.prev;
  64.             first.prev = second;
  65.             first.nextSibling = second.leftChild;
  66.             if (first.nextSibling != null)
  67.                 first.nextSibling.prev = first;
  68.             second.leftChild = first;
  69.             return second;
  70.         }
  71.         else
  72.         {
  73.             /* Attach second as leftmost child of first */
  74.             second.prev = first;
  75.             first.nextSibling = second.nextSibling;
  76.             if (first.nextSibling != null)
  77.                 first.nextSibling.prev = first;
  78.             second.nextSibling = first.leftChild;
  79.             if (second.nextSibling != null)
  80.                 second.nextSibling.prev = second;
  81.             first.leftChild = second;
  82.             return first;
  83.         }
  84.     }
  85.     private PairNode combineSiblings(PairNode firstSibling)
  86.     {
  87.         if( firstSibling.nextSibling == null )
  88.             return firstSibling;
  89.         /* Store the subtrees in an array */
  90.         int numSiblings = 0;
  91.         for ( ; firstSibling != null; numSiblings++)
  92.         {
  93.             treeArray = doubleIfFull( treeArray, numSiblings );
  94.             treeArray[ numSiblings ] = firstSibling;
  95.             /* break links */
  96.             firstSibling.prev.nextSibling = null;  
  97.             firstSibling = firstSibling.nextSibling;
  98.         }
  99.         treeArray = doubleIfFull( treeArray, numSiblings );
  100.         treeArray[ numSiblings ] = null;
  101.         /* Combine subtrees two at a time, going left to right */
  102.         int i = 0;
  103.         for ( ; i + 1 < numSiblings; i += 2)
  104.             treeArray[ i ] = compareAndLink(treeArray[i], treeArray[i + 1]);
  105.         int j = i - 2;
  106.         /* j has the result of last compareAndLink */
  107.         /* If an odd number of trees, get the last one */
  108.         if (j == numSiblings - 3)
  109.             treeArray[ j ] = compareAndLink( treeArray[ j ], treeArray[ j + 2 ] );
  110.         /* Now go right to left, merging last tree with */
  111.         /* next to last. The result becomes the new last */
  112.         for ( ; j >= 2; j -= 2)
  113.             treeArray[j - 2] = compareAndLink(treeArray[j-2], treeArray[j]);
  114.         return treeArray[0];
  115.     }
  116.     private PairNode[] doubleIfFull(PairNode [ ] array, int index)
  117.     {
  118.         if (index == array.length)
  119.         {
  120.             PairNode [ ] oldArray = array;
  121.             array = new PairNode[index * 2];
  122.             for( int i = 0; i < index; i++ )
  123.                 array[i] = oldArray[i];
  124.         }
  125.         return array;
  126.     }
  127.     /* Delete min element */
  128.     public int deleteMin( )
  129.     {
  130.         if (isEmpty( ) )
  131.             return -1;
  132.         int x = root.element;
  133.         if (root.leftChild == null)
  134.             root = null;
  135.         else
  136.             root = combineSiblings( root.leftChild );
  137.         return x;
  138.     }
  139.     /* inorder traversal */
  140.     public void inorder()
  141.     {
  142.         inorder(root);
  143.     }
  144.     private void inorder(PairNode r)
  145.     {
  146.         if (r != null)
  147.         {
  148.             inorder(r.leftChild);
  149.             System.out.print(r.element +" ");
  150.             inorder(r.nextSibling);
  151.         }
  152.     }
  153. }
  154.  
  155. /* Class PairHeapTest */
  156. public class PairHeapTest
  157. {
  158.     public static void main(String[] args)
  159.     {
  160.         Scanner scan = new Scanner(System.in);
  161.         System.out.println("PairHeap Test\n\n");        
  162.         PairHeap ph = new PairHeap();
  163.  
  164.         char ch;
  165.         /*  Perform PairHeap operations  */
  166.         do    
  167.         {
  168.             System.out.println("\nPair Heap Operations\n");
  169.             System.out.println("1. insert ");
  170.             System.out.println("2. delete min");
  171.             System.out.println("3. check empty");            
  172.             System.out.println("4. clear");
  173.  
  174.             int choice = scan.nextInt();            
  175.             switch (choice)
  176.             {
  177.             case 1 : 
  178.                 System.out.println("Enter integer element to insert");
  179.                 ph.insert( scan.nextInt() );                                    
  180.                 break;                          
  181.             case 2 : 
  182.                 ph.deleteMin();
  183.                 break;                         
  184.             case 3 : 
  185.                 System.out.println("Empty status = "+ ph.isEmpty());
  186.                 break;   
  187.             case 4 : 
  188.                 ph.makeEmpty();
  189.                 break;           
  190.             default : 
  191.                 System.out.println("Wrong Entry \n ");
  192.                 break;   
  193.             }
  194.             /* Display heap */
  195.             System.out.print("\nInorder Traversal : ");
  196.             ph.inorder();  
  197.  
  198.             System.out.println("\nDo you want to continue (Type y or n) \n");
  199.             ch = scan.next().charAt(0);                        
  200.         } while (ch == 'Y'|| ch == 'y');  
  201.     }
  202. }

PairHeap Test
 
 
 
Pair Heap Operations
 
1. insert
2. delete min
3. check empty
4. clear
1
Enter integer element to insert
67
 
Inorder Traversal : 67
Do you want to continue (Type y or n)
 
y
 
Pair Heap Operations
 
1. insert
2. delete min
3. check empty
4. clear
1
Enter integer element to insert
23
 
Inorder Traversal : 67 23
Do you want to continue (Type y or n)
 
y
 
Pair Heap Operations
 
1. insert
2. delete min
3. check empty
4. clear
1
Enter integer element to insert
12
 
Inorder Traversal : 67 23 12
Do you want to continue (Type y or n)
 
y
 
Pair Heap Operations
 
1. insert
2. delete min
3. check empty
4. clear
1
Enter integer element to insert
6
 
Inorder Traversal : 67 23 12 6
Do you want to continue (Type y or n)
 
y
 
Pair Heap Operations
 
1. insert
2. delete min
3. check empty
4. clear
1
Enter integer element to insert
78
 
Inorder Traversal : 78 67 23 12 6
Do you want to continue (Type y or n)
 
y
 
Pair Heap Operations
 
1. insert
2. delete min
3. check empty
4. clear
1
Enter integer element to insert
34
 
Inorder Traversal : 34 78 67 23 12 6
Do you want to continue (Type y or n)
 
y
 
Pair Heap Operations
 
1. insert
2. delete min
3. check empty
4. clear
1
Enter integer element to insert
45
 
Inorder Traversal : 45 34 78 67 23 12 6
Do you want to continue (Type y or n)
 
y
 
Pair Heap Operations
 
1. insert
2. delete min
3. check empty
4. clear
1
Enter integer element to insert
98
 
Inorder Traversal : 98 45 34 78 67 23 12 6
Do you want to continue (Type y or n)
 
y
 
Pair Heap Operations
 
1. insert
2. delete min
3. check empty
4. clear
1
Enter integer element to insert
67
 
Inorder Traversal : 67 98 45 34 78 67 23 12 6
Do you want to continue (Type y or n)
 
y
 
Pair Heap Operations
 
1. insert
2. delete min
3. check empty
4. clear
2
 
Inorder Traversal : 98 67 45 34 78 67 23 12
Do you want to continue (Type y or n)
 
y
 
Pair Heap Operations
 
1. insert
2. delete min
3. check empty
4. clear
2
 
Inorder Traversal : 98 67 45 34 78 67 23
Do you want to continue (Type y or n)
 
y
 
Pair Heap Operations
 
1. insert
2. delete min
3. check empty
4. clear
2
 
Inorder Traversal : 67 78 98 67 45 34
Do you want to continue (Type y or n)
 
y
 
Pair Heap Operations
 
1. insert
2. delete min
3. check empty
4. clear
2
 
Inorder Traversal : 78 67 98 67 45
Do you want to continue (Type y or n)
 
y
 
Pair Heap Operations
 
1. insert
2. delete min
3. check empty
4. clear
4
 
Inorder Traversal :
Do you want to continue (Type y or n)
 
y
 
Pair Heap Operations
 
1. insert
2. delete min
3. check empty
4. clear
3
Empty status = true
 
Inorder Traversal :
Do you want to continue (Type y or n)
 
n

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.