Java Program to Implement Ternary Heap

This is a Java Program to implement Ternary Heap. Here Ternary Heap is implemented using concept of D-ary Heap.

Here is the source code of the Java program to implement Ternary 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 Ternary-Heap
  3.  */
  4.  
  5. import java.util.Scanner;
  6. import java.util.Arrays;
  7. import java.util.NoSuchElementException;
  8.  
  9. /** Class Ternary Heap **/
  10. class TernaryHeap    
  11. {
  12.     private int d;
  13.     private int heapSize;
  14.     private int[] heap;
  15.  
  16.     /** Constructor **/    
  17.     public TernaryHeap  (int capacity, int numChild)
  18.     {
  19.         heapSize = 0;
  20.         d = numChild;
  21.         heap = new int[capacity + 1];
  22.         Arrays.fill(heap, -1);
  23.     }
  24.  
  25.     /** Function to check if heap is empty **/
  26.     public boolean isEmpty( )
  27.     {
  28.         return heapSize == 0;
  29.     }
  30.  
  31.     /** Check if heap is full **/
  32.     public boolean isFull( )
  33.     {
  34.         return heapSize == heap.length;
  35.     }
  36.  
  37.     /** Clear heap */
  38.     public void clear( )
  39.     {
  40.         heapSize = 0;
  41.     }
  42.  
  43.     /** Function to  get index parent of i **/
  44.     private int parent(int i) 
  45.     {
  46.         return (i - 1)/d;
  47.     }
  48.  
  49.     /** Function to get index of k th child of i **/
  50.     private int kthChild(int i, int k) 
  51.     {
  52.         return d * i + k;
  53.     }
  54.  
  55.     /** Function to insert element */
  56.     public void insert(int x)
  57.     {
  58.         if (isFull( ) )
  59.             throw new NoSuchElementException("Overflow Exception");
  60.         /** Percolate up **/
  61.         heap[heapSize++] = x;
  62.         heapifyUp(heapSize - 1);
  63.     }
  64.  
  65.     /** Function to find least element **/
  66.     public int findMin( )
  67.     {
  68.         if (isEmpty() )
  69.             throw new NoSuchElementException("Underflow Exception");           
  70.         return heap[0];
  71.     }
  72.  
  73.     /** Function to delete element at an index **/
  74.     public int delete(int ind)
  75.     {
  76.         if (isEmpty() )
  77.             throw new NoSuchElementException("Underflow Exception");
  78.         int keyItem = heap[ind];
  79.         heap[ind] = heap[heapSize - 1];
  80.         heapSize--;
  81.         heapifyDown(ind);        
  82.         return keyItem;
  83.     }
  84.  
  85.     /** Function heapifyUp  **/
  86.     private void heapifyUp(int childInd)
  87.     {
  88.         int tmp = heap[childInd];    
  89.         while (childInd > 0 && tmp < heap[parent(childInd)])
  90.         {
  91.             heap[childInd] = heap[ parent(childInd) ];
  92.             childInd = parent(childInd);
  93.         }                   
  94.         heap[childInd] = tmp;
  95.     }
  96.  
  97.     /** Function heapifyDown **/
  98.     private void heapifyDown(int ind)
  99.     {
  100.         int child;
  101.         int tmp = heap[ ind ];
  102.         while (kthChild(ind, 1) < heapSize)
  103.         {
  104.             child = minChild(ind);
  105.             if (heap[child] < tmp)
  106.                 heap[ind] = heap[child];
  107.             else
  108.                 break;
  109.             ind = child;
  110.         }
  111.         heap[ind] = tmp;
  112.     }
  113.  
  114.     /** Function to get smallest child **/
  115.     private int minChild(int ind) 
  116.     {
  117.         int bestChild = kthChild(ind, 1);
  118.         int k = 2;
  119.         int pos = kthChild(ind, k);
  120.         while ((k <= d) && (pos < heapSize)) 
  121.         {
  122.             if (heap[pos] < heap[bestChild]) 
  123.                 bestChild = pos;
  124.             pos = kthChild(ind, k++);
  125.         }    
  126.         return bestChild;
  127.     }
  128.  
  129.     /** Function to print heap **/
  130.     public void printHeap()
  131.     {
  132.         System.out.print("\nHeap = ");
  133.         for (int i = 0; i < heapSize; i++)
  134.             System.out.print(heap[i] +" ");
  135.         System.out.println();
  136.     }     
  137. }
  138.  
  139. /** Class TernaryHeapTest **/
  140. public class TernaryHeapTest
  141. {
  142.     public static void main(String[] args)
  143.     {
  144.         Scanner scan = new Scanner(System.in);
  145.         System.out.println("Ternary Heap Test\n\n");
  146.         System.out.println("Enter size and no of nodes each child has");
  147.         /** Make object of TernaryHeapHeap **/
  148.         TernaryHeap th = new TernaryHeap(scan.nextInt(), scan.nextInt() );
  149.  
  150.         char ch;
  151.         /**  Perform Ternary Heap operations **/
  152.         do    
  153.         {
  154.             System.out.println("\nTernary Heap Operations\n");
  155.             System.out.println("1. insert ");
  156.             System.out.println("2. delete");
  157.             System.out.println("3. check full");            
  158.             System.out.println("4. check empty");
  159.             System.out.println("5. clear");
  160.  
  161.             boolean chk;       
  162.             int choice = scan.nextInt();            
  163.             switch (choice)
  164.             {
  165.             case 1 : 
  166.                 try
  167.                 {
  168.                     System.out.println("Enter integer element to insert");
  169.                     th.insert( scan.nextInt() ); 
  170.                 }
  171.                 catch (Exception e)
  172.                 {
  173.                     System.out.println(e.getMessage() );
  174.                 }    
  175.                 break;                          
  176.             case 2 : 
  177.                 try
  178.                 {
  179.                     System.out.println("Enter delete position");
  180.                     th.delete(scan.nextInt() - 1); 
  181.                 }
  182.                 catch (Exception e)
  183.                 {
  184.                     System.out.println(e.getMessage() );
  185.                 }                 
  186.                 break;                         
  187.             case 3 : 
  188.                 System.out.println("Full status = "+ th.isFull());
  189.                 break;                                   
  190.             case 4 : 
  191.                 System.out.println("Empty status = "+ th.isEmpty());
  192.                 break; 
  193.             case 5 : 
  194.                 th.clear(); 
  195.                 System.out.println("Heap Cleared\n");
  196.                 break;         
  197.             default : 
  198.                 System.out.println("Wrong Entry \n ");
  199.                 break;   
  200.             } 
  201.             /** Display heap **/
  202.             th.printHeap();  
  203.  
  204.             System.out.println("\nDo you want to continue (Type y or n) \n");
  205.             ch = scan.next().charAt(0);                        
  206.         } while (ch == 'Y'|| ch == 'y');  
  207.     }
  208. }

Ternary Heap Test
 
 
Enter size and no of nodes each child has
3 3
 
Ternary Heap Operations
 
1. insert
2. delete
3. check full
4. check empty
5. clear
1
Enter integer element to insert
57
 
Heap = 57
 
Do you want to continue (Type y or n)
 
y
 
Ternary Heap Operations
 
1. insert
2. delete
3. check full
4. check empty
5. clear
1
Enter integer element to insert
17
 
Heap = 17 57
 
Do you want to continue (Type y or n)
 
y
 
Ternary Heap Operations
 
1. insert
2. delete
3. check full
4. check empty
5. clear
1
Enter integer element to insert
19
 
Heap = 17 57 19
 
Do you want to continue (Type y or n)
 
y
 
Ternary Heap Operations
 
1. insert
2. delete
3. check full
4. check empty
5. clear
1
Enter integer element to insert
7
 
Heap = 7 57 19 17
 
Do you want to continue (Type y or n)
 
y
 
Ternary Heap Operations
 
1. insert
2. delete
3. check full
4. check empty
5. clear
1
Enter integer element to insert
24
Overflow Exception
 
Heap = 7 57 19 17
 
Do you want to continue (Type y or n)
 
y
 
Ternary Heap Operations
 
1. insert
2. delete
3. check full
4. check empty
5. clear
2
Enter delete position
2
 
Heap = 7 17 19
 
Do you want to continue (Type y or n)
 
y
 
Ternary Heap Operations
 
1. insert
2. delete
3. check full
4. check empty
5. clear
2
Enter delete position
1
 
Heap = 17 19
 
Do you want to continue (Type y or n)
 
y
 
Ternary Heap Operations
 
1. insert
2. delete
3. check full
4. check empty
5. clear
2
Enter delete position
2
 
Heap = 17
 
Do you want to continue (Type y or n)
 
y
 
Ternary Heap Operations
 
1. insert
2. delete
3. check full
4. check empty
5. clear
4
Empty status = false
 
Heap = 17
 
Do you want to continue (Type y or n)
 
y
 
Ternary Heap Operations
 
1. insert
2. delete
3. check full
4. check empty
5. clear
5
Heap Cleared
 
 
Heap =
 
Do you want to continue (Type y or n)
 
y
 
Ternary Heap Operations
 
1. insert
2. delete
3. check full
4. check empty
5. clear
4
Empty status = true
 
Heap =
 
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.