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
heapSort(arr):
n = arr.length
// Build heap (rearrange array)
for i = n / 2 - 1 down to 0
heapify(arr, n, i)
// One by one extract an element from heap
for i = n-1 down to 1
// Move current root to end
swap arr[0] with arr[i]
// call max heapify on the reduced heap
heapify(arr, i, 0)
heapify(arr, n, i):
largest = i // Initialize largest as root
l = 2 * i + 1 // left = 2*i + 1
r = 2 * i + 2 // right = 2*i + 2
// If left child is larger than root
if l < n and arr[l] > arr[largest]
largest = l
// If right child is larger than largest so far
if r < n and arr[r] > arr[largest]
largest = r
// If largest is not root
if largest != i
swap arr[i] with arr[largest]
// Recursively heapify the affected sub-tree
heapify(arr, n, largest)
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.
/**
* Java Program to Implement Heap
*/
import java.util.Scanner;
/** Class Heap */
class Heap
{
private int[] heapArray;
/** size of array **/
private int maxSize;
/** number of nodes in array **/
private int heapSize;
/** Constructor **/
public Heap(int mx)
{
maxSize = mx;
heapSize = 0;
heapArray = new int[maxSize];
}
/** Check if heap is empty **/
public boolean isEmpty()
{
return heapSize == 0;
}
/** Function to insert element **/
public boolean insert(int ele)
{
if (heapSize + 1 == maxSize)
return false;
heapArray[++heapSize] = ele;
int pos = heapSize;
while (pos != 1 && ele > heapArray[pos/2])
{
heapArray[pos] = heapArray[pos/2];
pos /=2;
}
heapArray[pos] = ele;
return true;
}
/** function to remove element **/
public int remove()
{
int parent, child;
int item, temp;
if (isEmpty() )
throw new RuntimeException("Error : Heap empty!");
item = heapArray[1];
temp = heapArray[heapSize--];
parent = 1;
child = 2;
while (child <= heapSize)
{
if (child < heapSize && heapArray[child] < heapArray[child + 1])
child++;
if (temp >= heapArray[child])
break;
heapArray[parent] = heapArray[child];
parent = child;
child *= 2;
}
heapArray[parent] = temp;
return item;
}
/** Function to print values **/
public void displayHeap()
{
/* Array format */
System.out.print("\nHeap array: ");
for(int i = 1; i <= heapSize; i++)
System.out.print(heapArray[i] +" ");
System.out.println("\n");
}
}
/** Class HeapTest **/
public class HeapTest
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("Heap Test\n\n");
System.out.println("Enter size of heap");
Heap h = new Heap(scan.nextInt() );
char ch;
/** Perform Heap operations **/
do
{
System.out.println("\nHeap Operations\n");
System.out.println("1. insert ");
System.out.println("2. delete item with max key ");
System.out.println("3. check empty");
boolean chk;
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
chk = h.insert( scan.nextInt() );
if (chk)
System.out.println("Insertion successful\n");
else
System.out.println("Insertion failed\n");
break;
case 2 :
System.out.println("Enter integer element to delete");
if (!h.isEmpty())
h.remove();
else
System.out.println("Error. Heap is empty\n");
break;
case 3 :
System.out.println("Empty status = "+ h.isEmpty());
break;
default :
System.out.println("Wrong Entry \n ");
break;
}
/** Display heap **/
h.displayHeap();
System.out.println("\nDo you want to continue (Type y or n) \n");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}
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:
- 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.
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:
- Priority queues, sorting, graph algorithms, data compression, and finding median can be efficiently implemented using the heap data structure in Java.
- The PriorityQueue class in Java uses a heap data structure for priority queue implementation.
- The heap data structure is widely used in Java applications for job scheduling, task management, and resource allocation.
- 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”.
- Practice Design & Analysis of Algorithms MCQ
- Check Data Structure Books
- Practice Computer Science MCQs
- Check Computer Science Books
- Check Programming Books