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:
Comparing Strings in Java
An Intro to Spring Cloud Zookeeper
Using the Map.Entry Java Class
Error Handling for REST with Spring
Tạo số và chuỗi ngẫu nhiên trong Java
Hướng dẫn sử dụng Lớp FilePermission trong java
Collect a Java Stream to an Immutable Collection
Spring Boot - Internationalization
Java Program to Emulate N Dice Roller
Lập trình đa luồng trong Java (Java Multi-threading)
Java Program to Remove the Edges in a Given Cyclic Graph such that its Linear Extension can be Found
New Features in Java 14
The Dining Philosophers Problem in Java
Hướng dẫn sử dụng lớp Console trong java
Java 8 StringJoiner
HashMap trong Java hoạt động như thế nào?
Prevent Brute Force Authentication Attempts with Spring Security
Initialize a HashMap in Java
ETags for REST with Spring
Jackson JSON Views
Java Program to Implement Vector API
Java Program to Implement LinkedHashMap API
Send email with JavaMail
Testing an OAuth Secured API with Spring MVC
Giới thiệu về Stream API trong Java 8
Java Program to Implement Ford–Fulkerson Algorithm
HttpClient 4 – Follow Redirects for POST
Java Program to Implement Stack
Handle EML file with JavaMail
Từ khóa static và final trong java
Java Program to Create a Balanced Binary Tree of the Incoming Data
Documenting a Spring REST API Using OpenAPI 3.0