Java Program to Implement Binary Heap

«
»
This is a Java Program to implement Binary Heap. A binary heap is a heap data structure created using a binary tree. It can be seen as a binary tree with two additional constraints:
i) The shape property: the tree is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled and if the last level of the tree is not complete, the nodes of that level are filled from left to right.
ii) The heap property: each node is greater than or equal to each of its children according to a comparison predicate defined for the data structure.
Here binary heap is implemented using arrays.

Here is the source code of the Java program to implement Binary 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 Binary Heap
  3.  */
  4.  
  5. import java.util.Scanner;
  6. import java.util.Arrays;
  7. import java.util.NoSuchElementException;
  8.  
  9. /** Class BinaryHeap **/
  10. class BinaryHeap    
  11. {
  12.     /** The number of children each node has **/
  13.     private static final int d = 2;
  14.     private int heapSize;
  15.     private int[] heap;
  16.  
  17.     /** Constructor **/    
  18.     public BinaryHeap(int capacity)
  19.     {
  20.         heapSize = 0;
  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 makeEmpty( )
  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 min element **/
  74.     public int deleteMin()
  75.     {
  76.         int keyItem = heap[0];
  77.         delete(0);
  78.         return keyItem;
  79.     }
  80.  
  81.     /** Function to delete element at an index **/
  82.     public int delete(int ind)
  83.     {
  84.         if (isEmpty() )
  85.             throw new NoSuchElementException("Underflow Exception");
  86.         int keyItem = heap[ind];
  87.         heap[ind] = heap[heapSize - 1];
  88.         heapSize--;
  89.         heapifyDown(ind);        
  90.         return keyItem;
  91.     }
  92.  
  93.     /** Function heapifyUp  **/
  94.     private void heapifyUp(int childInd)
  95.     {
  96.         int tmp = heap[childInd];    
  97.         while (childInd > 0 && tmp < heap[parent(childInd)])
  98.         {
  99.             heap[childInd] = heap[ parent(childInd) ];
  100.             childInd = parent(childInd);
  101.         }                   
  102.         heap[childInd] = tmp;
  103.     }
  104.  
  105.     /** Function heapifyDown **/
  106.     private void heapifyDown(int ind)
  107.     {
  108.         int child;
  109.         int tmp = heap[ ind ];
  110.         while (kthChild(ind, 1) < heapSize)
  111.         {
  112.             child = minChild(ind);
  113.             if (heap[child] < tmp)
  114.                 heap[ind] = heap[child];
  115.             else
  116.                 break;
  117.             ind = child;
  118.         }
  119.         heap[ind] = tmp;
  120.     }
  121.  
  122.     /** Function to get smallest child **/
  123.     private int minChild(int ind) 
  124.     {
  125.         int bestChild = kthChild(ind, 1);
  126.         int k = 2;
  127.         int pos = kthChild(ind, k);
  128.         while ((k <= d) && (pos < heapSize)) 
  129.         {
  130.             if (heap[pos] < heap[bestChild]) 
  131.                 bestChild = pos;
  132.             pos = kthChild(ind, k++);
  133.         }    
  134.         return bestChild;
  135.     }
  136.  
  137.     /** Function to print heap **/
  138.     public void printHeap()
  139.     {
  140.         System.out.print("\nHeap = ");
  141.         for (int i = 0; i < heapSize; i++)
  142.             System.out.print(heap[i] +" ");
  143.         System.out.println();
  144.     }     
  145. }
  146.  
  147. /** Class BinaryHeapTest **/
  148. public class BinaryHeapTest
  149. {
  150.     public static void main(String[] args)
  151.     {
  152.         Scanner scan = new Scanner(System.in);
  153.         System.out.println("Binary Heap Test\n\n");
  154.         System.out.println("Enter size of Binary heap");
  155.         /** Make object of BinaryHeap **/
  156.         BinaryHeap bh = new BinaryHeap(scan.nextInt() );
  157.  
  158.         char ch;
  159.         /**  Perform Binary Heap operations  **/
  160.         do    
  161.         {
  162.             System.out.println("\nBinary Heap Operations\n");
  163.             System.out.println("1. insert ");
  164.             System.out.println("2. delete min");
  165.             System.out.println("3. check full");            
  166.             System.out.println("4. check empty");
  167.             System.out.println("5. clear");
  168.  
  169.             int choice = scan.nextInt();            
  170.             switch (choice)
  171.             {
  172.             case 1 : 
  173.                 try
  174.                 {
  175.                     System.out.println("Enter integer element to insert");
  176.                     bh.insert( scan.nextInt() ); 
  177.                 }
  178.                 catch (Exception e)
  179.                 {
  180.                     System.out.println(e.getMessage() );
  181.                 }
  182.                 break;                          
  183.             case 2 : 
  184.                 try
  185.                 {
  186.                     System.out.println("Min Element : "+ bh.deleteMin()); 
  187.                 }
  188.                 catch (Exception e)
  189.                 {
  190.                     System.out.println(e.getMessage() );
  191.                 }                 
  192.                 break;                                
  193.             case 3 : 
  194.                 System.out.println("Full status = "+ bh.isFull());
  195.                 break;                                   
  196.             case 4 : 
  197.                 System.out.println("Empty status = "+ bh.isEmpty());
  198.                 break; 
  199.             case 5 : 
  200.                 bh.makeEmpty();
  201.                 System.out.println("Heap Cleared\n");
  202.                 break;         
  203.             default : 
  204.                 System.out.println("Wrong Entry \n ");
  205.                 break;   
  206.             }
  207.             /** Display heap **/
  208.             bh.printHeap();  
  209.  
  210.             System.out.println("\nDo you want to continue (Type y or n) \n");
  211.             ch = scan.next().charAt(0);                        
  212.         } while (ch == 'Y'|| ch == 'y');  
  213.     }
  214. }

advertisement
Binary Heap Test
 
 
Enter size of Binary heap
10
 
Binary Heap Operations
 
1. insert
2. delete min
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
 
Binary Heap Operations
 
1. insert
2. delete min
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
 
Binary Heap Operations
 
1. insert
2. delete min
3. check full
4. check empty
5. clear
1
Enter integer element to insert
28
 
Heap = 6 24 28
 
Do you want to continue (Type y or n)
 
y
 
Binary Heap Operations
 
1. insert
2. delete min
3. check full
4. check empty
5. clear
1
Enter integer element to insert
5
 
Heap = 5 6 28 24
 
Do you want to continue (Type y or n)
 
y
 
Binary Heap Operations
 
1. insert
2. delete min
3. check full
4. check empty
5. clear
1
Enter integer element to insert
63
 
Heap = 5 6 28 24 63
 
Do you want to continue (Type y or n)
 
y
 
Binary Heap Operations
 
1. insert
2. delete min
3. check full
4. check empty
5. clear
1
Enter integer element to insert
19
 
Heap = 5 6 19 24 63 28
 
Do you want to continue (Type y or n)
 
y
 
Binary Heap Operations
 
1. insert
2. delete min
3. check full
4. check empty
5. clear
1
Enter integer element to insert
94
 
Heap = 5 6 19 24 63 28 94
 
Do you want to continue (Type y or n)
 
y
 
Binary Heap Operations
 
1. insert
2. delete min
3. check full
4. check empty
5. clear
2
Min Element : 5
 
Heap = 6 24 19 94 63 28
 
Do you want to continue (Type y or n)
 
y
 
Binary Heap Operations
 
1. insert
2. delete min
3. check full
4. check empty
5. clear
2
Min Element : 6
 
Heap = 19 24 28 94 63
 
Do you want to continue (Type y or n)
 
y
 
Binary Heap Operations
 
1. insert
2. delete min
3. check full
4. check empty
5. clear
2
Min Element : 19
 
Heap = 24 63 28 94
 
Do you want to continue (Type y or n)
 
y
 
Binary Heap Operations
 
1. insert
2. delete min
3. check full
4. check empty
5. clear
2
Min Element : 24
 
Heap = 28 63 94
 
Do you want to continue (Type y or n)
 
y
 
Binary Heap Operations
 
1. insert
2. delete min
3. check full
4. check empty
5. clear
2
Min Element : 28
 
Heap = 63 94
 
Do you want to continue (Type y or n)
 
y
 
Binary Heap Operations
 
1. insert
2. delete min
3. check full
4. check empty
5. clear
2
Min Element : 63
 
Heap = 94
 
Do you want to continue (Type y or n)
 
y
 
Binary Heap Operations
 
1. insert
2. delete min
3. check full
4. check empty
5. clear
2
Min Element : 94
 
Heap =
 
Do you want to continue (Type y or n)
 
y
 
Binary Heap Operations
 
1. insert
2. delete min
3. check full
4. check empty
5. clear
2
Underflow Exception
 
Heap =
 
Do you want to continue (Type y or n)
 
y
 
Binary Heap Operations
 
1. insert
2. delete min
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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
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.