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 implement Circular Buffer
Spring Boot With H2 Database
Logout in an OAuth Secured Application
Java Program to implement Sparse Vector
Adding Parameters to HttpClient Requests
Java 8 StringJoiner
A Guide to the ViewResolver in Spring MVC
Java Program to Generate Date Between Given Range
Java Program to Use Dynamic Programming to Solve Approximate String Matching
Spring Boot - Enabling Swagger2
Spring – Injecting Collections
Java Program to Implement Miller Rabin Primality Test Algorithm
Converting a Stack Trace to a String in Java
Java Program to find the peak element of an array using Binary Search approach
Java Program to Implement AA Tree
Build a REST API with Spring and Java Config
Java Program to Perform Right Rotation on a Binary Search Tree
Converting Iterator to List
Arrays.asList vs new ArrayList(Arrays.asList())
Copy a List to Another List in Java
A Guide to JPA with Spring
Java Program to Implement K Way Merge Algorithm
Guide to java.util.concurrent.Future
Java Program to Find Number of Spanning Trees in a Complete Bipartite Graph
A Guide to Java HashMap
Java Program to Implement Sorted Doubly Linked List
Java – Generate Random String
Java Program to Implement Stack using Linked List
Java Program to Implement Skip List
Java Program to Implement ConcurrentSkipListMap API
Java Program to Implement Circular Doubly Linked List
How to Iterate Over a Stream With Indices