Java Program to Implement Heap

«
»
This is a Java Program to implement 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.

Here is the source code of the Java program to implement 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 Heap
  3.  */
  4.  
  5. import java.util.Scanner;
  6.  
  7. /** Class Heap */
  8. class Heap
  9. {
  10.  
  11.     private int[] heapArray;
  12.     /** size of array **/
  13.     private int maxSize; 
  14.     /** number of nodes in array **/
  15.     private int heapSize; 
  16.  
  17.     /** Constructor **/
  18.     public Heap(int mx) 
  19.     {
  20.         maxSize = mx;
  21.         heapSize = 0;
  22.         heapArray = new int[maxSize]; 
  23.     }
  24.     /** Check if heap is empty **/
  25.     public boolean isEmpty() 
  26.     {
  27.         return heapSize == 0;
  28.     }
  29.     /** Function to insert element **/
  30.     public boolean insert(int ele) 
  31.     {
  32.         if (heapSize + 1 == maxSize)
  33.             return false;
  34.         heapArray[++heapSize] = ele;
  35.         int pos = heapSize;
  36.         while (pos != 1 && ele > heapArray[pos/2])
  37.         {
  38.             heapArray[pos] = heapArray[pos/2];
  39.             pos /=2;
  40.         }
  41.         heapArray[pos] = ele;    
  42.         return true;
  43.     } 
  44.  
  45.     /** function to remove element **/
  46.     public int remove()
  47.     {
  48.         int parent, child;
  49.         int item, temp;
  50.         if (isEmpty() )
  51.             throw new RuntimeException("Error : Heap empty!");
  52.  
  53.         item = heapArray[1];
  54.         temp = heapArray[heapSize--];
  55.  
  56.         parent = 1;
  57.         child = 2;
  58.         while (child <= heapSize)
  59.         {
  60.             if (child < heapSize && heapArray[child] < heapArray[child + 1])
  61.                 child++;
  62.             if (temp >= heapArray[child])
  63.                 break;
  64.  
  65.             heapArray[parent] = heapArray[child];
  66.             parent = child;
  67.             child *= 2;
  68.         }
  69.         heapArray[parent] = temp;
  70.  
  71.         return item;
  72.     }
  73.  
  74.     /** Function to print values **/
  75.     public void displayHeap()
  76.     {
  77.         /* Array format */
  78.         System.out.print("\nHeap array: ");    
  79.         for(int i = 1; i <= heapSize; i++)
  80.             System.out.print(heapArray[i] +" ");
  81.         System.out.println("\n");
  82.     }  
  83. }
  84.  
  85. /** Class HeapTest **/
  86. public class HeapTest
  87. {
  88.     public static void main(String[] args)
  89.     {
  90.         Scanner scan = new Scanner(System.in);
  91.         System.out.println("Heap Test\n\n");
  92.         System.out.println("Enter size of heap");
  93.         Heap h = new Heap(scan.nextInt() );
  94.  
  95.         char ch;
  96.         /**  Perform Heap operations  **/
  97.         do    
  98.         {
  99.             System.out.println("\nHeap Operations\n");
  100.             System.out.println("1. insert ");
  101.             System.out.println("2. delete item with max key ");
  102.             System.out.println("3. check empty");
  103.  
  104.             boolean chk;       
  105.             int choice = scan.nextInt();            
  106.             switch (choice)
  107.             {
  108.             case 1 : 
  109.                 System.out.println("Enter integer element to insert");
  110.                 chk = h.insert( scan.nextInt() ); 
  111.                 if (chk)
  112.                     System.out.println("Insertion successful\n");
  113.                 else
  114.                     System.out.println("Insertion failed\n");                    
  115.                 break;                          
  116.             case 2 : 
  117.                 System.out.println("Enter integer element to delete");
  118.                 if (!h.isEmpty())
  119.                     h.remove();
  120.                 else
  121.                     System.out.println("Error. Heap is empty\n");   
  122.                 break;                         
  123.             case 3 : 
  124.                 System.out.println("Empty status = "+ h.isEmpty());
  125.                 break;         
  126.             default : 
  127.                 System.out.println("Wrong Entry \n ");
  128.                 break;       
  129.             }
  130.  
  131.             /** Display heap **/
  132.             h.displayHeap();  
  133.  
  134.             System.out.println("\nDo you want to continue (Type y or n) \n");
  135.             ch = scan.next().charAt(0);                        
  136.         } while (ch == 'Y'|| ch == 'y');  
  137.     }
  138. }

advertisement
Heap Test
 
 
Enter size of heap
10
 
Heap Operations
 
1. insert
2. delete item with max key
3. check empty
1
Enter integer element to insert
7
Insertion successful
 
 
Heap array: 7
 
 
Do you want to continue (Type y or n)
 
y
 
Heap Operations
 
1. insert
2. delete item with max key
3. check empty
1
Enter integer element to insert
3
Insertion successful
 
 
Heap array: 7 3
 
 
Do you want to continue (Type y or n)
 
y
 
Heap Operations
 
1. insert
2. delete item with max key
3. check empty
1
Enter integer element to insert
2
Insertion successful
 
 
Heap array: 7 3 2
 
 
Do you want to continue (Type y or n)
 
y
 
Heap Operations
 
1. insert
2. delete item with max key
3. check empty
1
Enter integer element to insert
5
Insertion successful
 
 
Heap array: 7 5 2 3
 
 
Do you want to continue (Type y or n)
 
y
 
Heap Operations
 
1. insert
2. delete item with max key
3. check empty
1
Enter integer element to insert
8
Insertion successful
 
 
Heap array: 8 7 2 3 5
 
 
Do you want to continue (Type y or n)
 
y
 
Heap Operations
 
1. insert
2. delete item with max key
3. check empty
1
Enter integer element to insert
1
Insertion successful
 
 
Heap array: 8 7 2 3 5 1
 
 
Do you want to continue (Type y or n)
 
y
 
Heap Operations
 
1. insert
2. delete item with max key
3. check empty
1
Enter integer element to insert
9
Insertion successful
 
 
Heap array: 9 7 8 3 5 1 2
 
 
Do you want to continue (Type y or n)
 
y
 
Heap Operations
 
1. insert
2. delete item with max key
3. check empty
2
Enter integer element to delete
 
Heap array: 8 7 2 3 5 1
 
 
Do you want to continue (Type y or n)
 
y
 
Heap Operations
 
1. insert
2. delete item with max key
3. check empty
2
Enter integer element to delete
 
Heap array: 7 5 2 3 1
 
 
Do you want to continue (Type y or n)
 
y
 
Heap Operations
 
1. insert
2. delete item with max key
3. check empty
2
Enter integer element to delete
 
Heap array: 5 3 2 1
 
 
Do you want to continue (Type y or n)
 
y
 
Heap Operations
 
1. insert
2. delete item with max key
3. check empty
2
Enter integer element to delete
 
Heap array: 3 1 2
 
 
Do you want to continue (Type y or n)
 
y
 
Heap Operations
 
1. insert
2. delete item with max key
3. check empty
2
Enter integer element to delete
 
Heap array: 2 1
 
 
Do you want to continue (Type y or n)
 
y
 
Heap Operations
 
1. insert
2. delete item with max key
3. check empty
2
Enter integer element to delete
 
Heap array: 1
 
 
Do you want to continue (Type y or n)
 
y
 
Heap Operations
 
1. insert
2. delete item with max key
3. check empty
2
Enter integer element to delete
 
Heap array:
 
 
Do you want to continue (Type y or n)
 
y
 
Heap Operations
 
1. insert
2. delete item with max key
3. check empty
2
Enter integer element to delete
Error. Heap is empty
 
 
Heap array:
 
 
Do you want to continue (Type y or n)
 
y
 
Heap Operations
 
1. insert
2. delete item with max key
3. check empty
3
Empty status = true
 
Heap array:
 
 
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.