How to Implement Min-Heap in Java
- Implementation of Min Heap Without Using Library in Java
-
Implementation of Min-Heap Using
PriorityQueuein Java
A Min Heap is a Heap in which each internal node is smaller than or equal to its children’s values. We will see how to implement Min Heap with and without using a library in the following points.
Implementation of Min Heap Without Using Library in Java
In this example, we see the implementation without using any library. Here we create a class JavaMinHeap in which we create three instance variables HeapArray is an int type array that will keep all the values of the heap, size is the size of the heap, maxSize stores the maximum size of the HeapArray. We also create a static variable FRONT of type int and initialize it with 1.
We get maxSize as a parameter in the constructor and store it in the instance variable maxSize. We initialize size with 0 and HeapArray with an array of int with the size of maxSize + 1. We store the minimum value of Integer at the first index of HeapArray.
Now we create methods to perform operations on the heap. parent() function takes a position as a parameter and returns the parent of the passed position of the node. Then we create leftChild() that returns the left child of the position received as a parameter. Same goes for the right child using rightChild() that returns the (2 * position) + 1 node’s value.
isLeaf() checks if a node is a leaf node or not, which means it has any child. swapNodes() is a method that swaps the node’s value of position fpos with the position spos. In the method, we create a temp variable and initialize it, the fpos position of HeapArray and store the spos value of HeapArray to HeapArray[fpos]. Now we store the temp value in HeapArray[spos].
convertToMinHeap() checks if the position received as a parameter is a leaf or not using isLeaf and if not, then checks if the current value at the position of HeapArray is greater than the left child or the right child. Then we check if the left child is smaller than the right child, and if it is, we use swapNodes() to swap the nodes and pass the position and the left child at position. We again convert the received left child to min heap using convertToMinHeap().
We use insert() to insert the values to the min-heap. In insert() we return without inserting if the array reached maxSize; if not, we get the position at ++size and insert the received element at HeapArray[++size]. We put size to current. We create a loop and swap nodes if the element at the current position is smaller than its parent.
To print the min-heap, we create printheap() and loop through the HeapArray where the parent is at the ith position, the left child is at the 2 * i position, and the right child is at the 2 * i + 1 position. In the main() function, we use insert() to insert elements in heap.
public class JavaMinHeap {
private final int[] HeapArray;
private int size;
private final int maxsize;
private static final int FRONT = 1;
public JavaMinHeap(int maxsize) {
this.maxsize = maxsize;
this.size = 0;
HeapArray = new int[this.maxsize + 1];
HeapArray[0] = Integer.MIN_VALUE;
}
private int parent(int position) {
return position / 2;
}
private int leftChild(int position) {
return (2 * position);
}
private int rightChild(int position) {
return (2 * position) + 1;
}
private boolean isLeaf(int position) {
if (position >= (size / 2) && position <= size) {
return true;
}
return false;
}
private void swapNodes(int fpos, int spos) {
int temp;
temp = HeapArray[fpos];
HeapArray[fpos] = HeapArray[spos];
HeapArray[spos] = temp;
}
private void convertToMinHeap(int position) {
if (!isLeaf(position)) {
if (HeapArray[position] > HeapArray[leftChild(position)]
|| HeapArray[position] > HeapArray[rightChild(position)]) {
if (HeapArray[leftChild(position)] < HeapArray[rightChild(position)]) {
swapNodes(position, leftChild(position));
convertToMinHeap(leftChild(position));
} else {
swapNodes(position, rightChild(position));
convertToMinHeap(rightChild(position));
}
}
}
}
public void insert(int element) {
if (size >= maxsize) {
return;
}
HeapArray[++size] = element;
int current = size;
while (HeapArray[current] < HeapArray[parent(current)]) {
swapNodes(current, parent(current));
current = parent(current);
}
}
public void printHeap() {
for (int i = 1; i <= size / 2; i++) {
System.out.println("PARENT : " + HeapArray[i]);
System.out.println("--LEFT CHILD : " + HeapArray[2 * i]);
System.out.println("--RIGHT CHILD : " + HeapArray[2 * i + 1]);
System.out.println();
}
}
public static void main(String[] arg) {
System.out.println("The Min Heap is ");
JavaMinHeap minHeap = new JavaMinHeap(10);
minHeap.insert(10);
minHeap.insert(2);
minHeap.insert(7);
minHeap.insert(15);
minHeap.insert(90);
minHeap.insert(19);
minHeap.insert(8);
minHeap.insert(22);
minHeap.insert(9);
minHeap.printHeap();
}
}
Output:
The Min Heap is
PARENT : 2
--LEFT CHILD : 9
--RIGHT CHILD : 7
PARENT : 9
--LEFT CHILD : 10
--RIGHT CHILD : 90
PARENT : 7
--LEFT CHILD : 19
--RIGHT CHILD : 8
PARENT : 10
--LEFT CHILD : 22
--RIGHT CHILD : 15
Implementation of Min-Heap Using PriorityQueue in Java
In this program, we use PriorityQueue that is used to create max and min heaps. PriorityQueue provides multiple like add() that inserts the element to the queue, peek() fetches the head of the queue and removes it, poll() also retrieves the head of the queue but without removing it. contains() checks it the specified element is the queue. remove() removes the specified element.
We combine all the functions of PriorityQueue to create and perform min-heap operations. First we create an empty priorityQueue object of Integer type using new PriorityQueue(). Then we add our elements using the add() method. To print and remove the queue head, we call priorityQueue.peek() that prints 10. Then we print all the elements of the queue using enhanced for. Now we call poll() that prints and removes 10. Then we remove an element from the queue. We use contains() that returns a boolean to check if an element is in the queue. At last, to print the remaining value we convert the queue to an array using toArray().
import java.util.*;
public class JavaMinHeap {
public static void main(String[] args) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.add(10);
priorityQueue.add(15);
priorityQueue.add(25);
priorityQueue.add(200);
System.out.println("The head value using peek(): " + priorityQueue.peek());
System.out.println("The queue elements: ");
for (Integer integer : priorityQueue) System.out.println(integer);
priorityQueue.poll();
System.out.println("After removing the head element using poll(): ");
for (Integer integer : priorityQueue) System.out.println(integer);
priorityQueue.remove(25);
System.out.println("After removing 25 with remove(): ");
for (Integer integer : priorityQueue) System.out.println(integer);
boolean b = priorityQueue.contains(15);
System.out.println("Check if priorityQueue contains 15 using contains(): " + b);
Object[] arr = priorityQueue.toArray();
System.out.println("Values in array: ");
for (Object o : arr) System.out.println("Value: " + o.toString());
}
}
Output:
The head value using peek(): 10
The queue elements:
10
15
25
200
After removing the head element using poll():
15
200
25
After removing 25 with remove():
15
200
Check if priorityQueue contains 15 using contains(): true
Values in array:
Value: 15
Value: 200
Rupam Saini is an android developer, who also works sometimes as a web developer., He likes to read books and write about various things.
LinkedIn