Java Program to Implement D-ary Heap

«
»
This is a Java Program to implement D-ary Heap. A heap is a specialized tree-based data structure that satisfies the heap property: If A is a parent node of B then key(A) is ordered with respect to key(B) with the same ordering applying across the heap. Either the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node (max heap) or the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node (min heap). Heaps are crucial in several efficient graph algorithms such as Dijkstra’s algorithm and in the sorting algorithm heapsort.
The d-ary heap or d-heap is a priority queue data structure, a generalization of the binary heap in which the nodes have d children instead of 2.

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

advertisement
D ary Heap Test
 
 
Enter size and D of D-ary Heap
6 3
 
D-ary Heap Operations
 
1. insert
2. delete
3. check full
4. check empty
5. clear
1
Enter integer element to insert
24
 
Heap = 24
 
Do you want to continue (Type y or n)
 
y
 
D-ary Heap Operations
 
1. insert
2. delete
3. check full
4. check empty
5. clear
1
Enter integer element to insert
6
 
Heap = 6 24
 
Do you want to continue (Type y or n)
 
y
 
D-ary Heap Operations
 
1. insert
2. delete
3. check full
4. check empty
5. clear
1
Enter integer element to insert
23
 
Heap = 6 24 23
 
Do you want to continue (Type y or n)
 
y
 
D-ary Heap Operations
 
1. insert
2. delete
3. check full
4. check empty
5. clear
1
Enter integer element to insert
12
 
Heap = 6 24 23 12
 
Do you want to continue (Type y or n)
 
y
 
D-ary Heap Operations
 
1. insert
2. delete
3. check full
4. check empty
5. clear
1
Enter integer element to insert
75
 
Heap = 6 24 23 12 75
 
Do you want to continue (Type y or n)
 
y
 
D-ary Heap Operations
 
1. insert
2. delete
3. check full
4. check empty
5. clear
1
Enter integer element to insert
78
 
Heap = 6 24 23 12 75 78
 
Do you want to continue (Type y or n)
 
y
 
D-ary Heap Operations
 
1. insert
2. delete
3. check full
4. check empty
5. clear
1
Enter integer element to insert
29
 
Heap = 6 24 23 12 75 78 29
 
Do you want to continue (Type y or n)
 
y
 
D-ary Heap Operations
 
1. insert
2. delete
3. check full
4. check empty
5. clear
2
Enter delete position
5
 
Heap = 6 24 23 12 29 78
 
Do you want to continue (Type y or n)
 
y
 
D-ary Heap Operations
 
1. insert
2. delete
3. check full
4. check empty
5. clear
2
Enter delete position
6
 
Heap = 6 24 23 12 29
 
Do you want to continue (Type y or n)
 
y
 
D-ary Heap Operations
 
1. insert
2. delete
3. check full
4. check empty
5. clear
2
Enter delete position
3
 
Heap = 6 24 29 12
 
Do you want to continue (Type y or n)
 
y
 
D-ary 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
 
D-ary 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.