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:
Collect a Java Stream to an Immutable Collection
Get the workstation name or IP
Check If a File or Directory Exists in Java
Java Program to Implement TreeSet API
Spring Boot - Batch Service
Xử lý ngoại lệ trong Java (Exception Handling)
Thao tác với tập tin và thư mục trong Java
Java Program to Perform Stooge Sort
The Guide to RestTemplate
Java Program to Represent Graph Using Linked List
Quick Guide to Spring Bean Scopes
Concrete Class in Java
Checked and Unchecked Exceptions in Java
Spring Autowiring of Generic Types
Custom Error Pages with Spring MVC
Hướng dẫn Java Design Pattern – Builder
Java Program to Represent Linear Equations in Matrix Form
Java Program to Implement Merge Sort Algorithm on Linked List
Adding Shutdown Hooks for JVM Applications
Java – Write to File
Converting String to Stream of chars
“Stream has already been operated upon or closed” Exception in Java
How to Return 404 with Spring WebFlux
Java Program to Implement IdentityHashMap API
Java Program to find the maximum subarray sum using Binary Search approach
Java Program to Perform Optimal Paranthesization Using Dynamic Programming
Spring Cloud AWS – EC2
HashMap trong Java hoạt động như thế nào?
Spring Security OAuth2 – Simple Token Revocation
A Custom Media Type for a Spring REST API
Hướng dẫn Java Design Pattern – Flyweight
Implementing a Binary Tree in Java