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. }

advertisement
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.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

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 & technical discussions at Telegram SanfoundryClasses.