This Java program is to implement Min heap. A Heap data structure is a 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.”
So in a Min Heap this property will be “If A is a parent node of B then key(A) is less than key(B) with the same ordering applying across the heap.” and in a max heap the key(A) will be greater than Key(B).
Here is the source code of the Java program to implement Min heap. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.
public class MinHeap
{
private int[] Heap;
private int size;
private int maxsize;
private static final int FRONT = 1;
public MinHeap(int maxsize)
{
this.maxsize = maxsize;
this.size = 0;
Heap = new int[this.maxsize + 1];
Heap[0] = Integer.MIN_VALUE;
}
private int parent(int pos)
{
return pos / 2;
}
private int leftChild(int pos)
{
return (2 * pos);
}
private int rightChild(int pos)
{
return (2 * pos) + 1;
}
private boolean isLeaf(int pos)
{
if (pos >= (size / 2) && pos <= size)
{
return true;
}
return false;
}
private void swap(int fpos, int spos)
{
int tmp;
tmp = Heap[fpos];
Heap[fpos] = Heap[spos];
Heap[spos] = tmp;
}
private void minHeapify(int pos)
{
if (!isLeaf(pos))
{
if ( Heap[pos] > Heap[leftChild(pos)] || Heap[pos] > Heap[rightChild(pos)])
{
if (Heap[leftChild(pos)] < Heap[rightChild(pos)])
{
swap(pos, leftChild(pos));
minHeapify(leftChild(pos));
}else
{
swap(pos, rightChild(pos));
minHeapify(rightChild(pos));
}
}
}
}
public void insert(int element)
{
Heap[++size] = element;
int current = size;
while (Heap[current] < Heap[parent(current)])
{
swap(current,parent(current));
current = parent(current);
}
}
public void print()
{
for (int i = 1; i <= size / 2; i++ )
{
System.out.print(" PARENT : " + Heap[i] + " LEFT CHILD : " + Heap[2*i]
+ " RIGHT CHILD :" + Heap[2 * i + 1]);
System.out.println();
}
}
public void minHeap()
{
for (int pos = (size / 2); pos >= 1 ; pos--)
{
minHeapify(pos);
}
}
public int remove()
{
int popped = Heap[FRONT];
Heap[FRONT] = Heap[size--];
minHeapify(FRONT);
return popped;
}
public static void main(String...arg)
{
System.out.println("The Min Heap is ");
MinHeap minHeap = new MinHeap(15);
minHeap.insert(5);
minHeap.insert(3);
minHeap.insert(17);
minHeap.insert(10);
minHeap.insert(84);
minHeap.insert(19);
minHeap.insert(6);
minHeap.insert(22);
minHeap.insert(9);
minHeap.minHeap();
minHeap.print();
System.out.println("The Min val is " + minHeap.remove());
}
}
$javac MinHeap.java $java MinHeap The Min Heap is PARENT : 3 LEFT CHILD : 5 RIGHT CHILD :6 PARENT : 5 LEFT CHILD : 9 RIGHT CHILD :84 PARENT : 6 LEFT CHILD : 19 RIGHT CHILD :17 PARENT : 9 LEFT CHILD : 22 RIGHT CHILD :10 The Min val is 3
Related posts:
Java Program to Check whether Graph is a Bipartite using 2 Color Algorithm
Convert Hex to ASCII in Java
Java – Try with Resources
Kiểu dữ liệu Ngày Giờ (Date Time) trong java
Java Program to Implement Heap’s Algorithm for Permutation of N Numbers
Abstract class và Interface trong Java
Java Program to Test Using DFS Whether a Directed Graph is Weakly Connected or Not
Apache Commons Collections MapUtils
Java 8 Streams peek() API
Guide to PriorityBlockingQueue in Java
A Guide to Java 9 Modularity
Adding Shutdown Hooks for JVM Applications
Automatic Property Expansion with Spring Boot
Introduction to Spring Data JPA
Getting a File’s Mime Type in Java
Java Program to Perform Right Rotation on a Binary Search Tree
Wrapper Classes in Java
Serverless Functions with Spring Cloud Function
Java Program to Create a Random Linear Extension for a DAG
Tạo số và chuỗi ngẫu nhiên trong Java
Java Program to Perform Inorder Non-Recursive Traversal of a Given Binary Tree
A Comparison Between Spring and Spring Boot
Java Program to Delete a Particular Node in a Tree Without Using Recursion
Java Program to Implement the Hill Cypher
Java Program to Apply Above-Below-on Test to Find the Position of a Point with respect to a Line
Deploy a Spring Boot WAR into a Tomcat Server
Send an email with an attachment
Java Program to Perform Finite State Automaton based Search
Guide to the ConcurrentSkipListMap
How to Remove the Last Character of a String?
A Guide to Java HashMap
Converting a Stack Trace to a String in Java