Java Program to Implement Heap

Problem Description

Write a Java Program to implement Heap.

What is Heap?
A Heap in java 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.

Types of Heaps in Java

  • Max heap: A max heap is a binary tree-based data structure in which the value of each parent node is greater than or equal to the value of its children. It is commonly used in sorting algorithms and priority queues.
  • Min heap: A min heap is like a tree where each parent has a value that’s either smaller or equal to the values of its children. Mainly helpful in sorting and organizing things in a specific order.

Heap Operations in Java
Heap operations are methods used in Java to manipulate and work with heap data structures. Some of the most common heap operations in Java include:

  • Insertion: Adding a new element to the heap.
  • Deletion: Removing an element from the heap.
  • Peek: Examining the root element of the heap without removing it.
  • Heapify: Transforming an array into a heap data structure.
  • Merge: Combining two heap data structures into one.

Heap Sort Algorithm

advertisement
advertisement
  1. heapSort(arr):
  2.     n = arr.length
  3.     // Build heap (rearrange array)
  4.     for i = n / 2 - 1 down to 0
  5.         heapify(arr, n, i)
  6.  
  7.     // One by one extract an element from heap
  8.     for i = n-1 down to 1
  9.         // Move current root to end
  10.         swap arr[0] with arr[i]
  11.  
  12.         // call max heapify on the reduced heap
  13.         heapify(arr, i, 0)
  14.  
  15. heapify(arr, n, i):
  16.     largest = i // Initialize largest as root
  17.     l = 2 * i + 1 // left = 2*i + 1
  18.     r = 2 * i + 2 // right = 2*i + 2
  19.  
  20.     // If left child is larger than root
  21.     if l < n and arr[l] > arr[largest]
  22.         largest = l
  23.  
  24.     // If right child is larger than largest so far
  25.     if r < n and arr[r] > arr[largest]
  26.         largest = r
  27.  
  28.     // If largest is not root
  29.     if largest != i
  30.         swap arr[i] with arr[largest]
  31.         // Recursively heapify the affected sub-tree
  32.         heapify(arr, n, largest)
Program/Source Code

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

1. The Heap class is defined to represent the heap data structure, and it contains a private integer array, a maxSize variable to keep track of the maximum size of the heap, and a heapSize variable to keep track of the current size of the heap.
2. A constructor is defined for the Heap class that initializes the maxSize and heapSize variables and creates a new array of integers of size equal to maxSize.
3. Methods used in the program:

Note: Join free Sanfoundry classes at Telegram or Youtube
  • isEmpty() method that returns true if the heap is empty, i.e., heapSize equals zero.
  • insert() method is defined, which takes an integer value as input and inserts it into the heap. It returns true if the insertion is successful and false if the heap is already full.
  • remove() method is defined, which removes the element with the maximum key from the heap and returns it. It throws a RuntimeException if the heap is already empty.
  • displayHeap() method that prints the heap array in a tree-like format.

4. The HeapTest class is defined, which contains the main() method that provides the user with a command-line interface to interact with the heap.
5. A do-while loop is used to display a menu of heap operations to the user. The user can choose from three operations: insert, delete, and check empty status.
6. The user’s input is read using the Scanner object, and the appropriate heap operation is performed based on the user’s choice.
7. The program asks the user if they want to continue using the heap. If the user types ‘y’ or ‘Y’, the loop continues, and the menu is displayed again. Otherwise, the loop terminates, and the program exits.

Program Output
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

Applications of Heaps in Java:

advertisement
  1. Priority queues, sorting, graph algorithms, data compression, and finding median can be efficiently implemented using the heap data structure in Java.
  2. The PriorityQueue class in Java uses a heap data structure for priority queue implementation.
  3. The heap data structure is widely used in Java applications for job scheduling, task management, and resource allocation.
  4. It is also used for priority scheduling of processes in operating systems and for compression and decompression of data.

To practice programs on every topic in Java, please visit “Programming Examples in Java”, “Data Structures in Java” and “Algorithms in Java”.

advertisement

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.