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 Sparse Array
Rate Limiting in Spring Cloud Netflix Zuul
Apache Commons Collections MapUtils
Java Program to Implement Interval Tree
Spring Boot - Google OAuth2 Sign-In
Java Program to Implement Find all Forward Edges in a Graph
Guide to Java 8 groupingBy Collector
Primitive Type Streams in Java 8
Spring Webflux with Kotlin
Java Program to Implement Red Black Tree
Java Program to Generate Random Numbers Using Probability Distribution Function
Convert XML to JSON Using Jackson
Java Program to Implement Booth Algorithm
New Features in Java 12
Java Program to Optimize Wire Length in Electrical Circuit
Servlet 3 Async Support with Spring MVC and Spring Security
Hướng dẫn Java Design Pattern – Bridge
Java 14 Record Keyword
Redirect to Different Pages after Login with Spring Security
Hướng dẫn Java Design Pattern – Abstract Factory
Java Program to Compute the Volume of a Tetrahedron Using Determinants
Working With Maps Using Streams
How to Get a Name of a Method Being Executed?
A Guide to Queries in Spring Data MongoDB
Java Program to Apply Above-Below-on Test to Find the Position of a Point with respect to a Line
Java Program to Implement HashTable API
Marker Interface trong Java
Java Program to Implement AVL Tree
Introduction to Spring Cloud Stream
REST Web service: Basic Authentication trong Jersey 2.x
Map to String Conversion in Java
Spring Boot - Thymeleaf