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 Perform Encoding of a Message Using Matrix Multiplication
Introduction to Java Serialization
Chuyển đổi từ HashMap sang ArrayList
Guide to Character Encoding
Java Program to Perform integer Partition for a Specific Case
Luồng Daemon (Daemon Thread) trong Java
wait() and notify() Methods in Java
Tính đóng gói (Encapsulation) trong java
Running Spring Boot Applications With Minikube
Introduction to PCollections
Spring Cloud – Securing Services
Testing in Spring Boot
Instance Profile Credentials using Spring Cloud
Overview of the java.util.concurrent
Creating Docker Images with Spring Boot
Java Program to Perform Searching in a 2-Dimension K-D Tree
Java Program to Construct an Expression Tree for an Postfix Expression
Hướng dẫn Java Design Pattern – Adapter
Java Program to Implement Horner Algorithm
Java Program to Implement the Monoalphabetic Cypher
Copy a List to Another List in Java
Java Program to Solve the 0-1 Knapsack Problem
Annotation trong Java 8
Java – Reader to String
Java Program to implement Bit Matrix
Quick Guide to Spring Bean Scopes
How to Remove the Last Character of a String?
Apache Tiles Integration with Spring MVC
Removing Elements from Java Collections
The Difference Between map() and flatMap()
Java Program to Implement Binomial Heap
Concrete Class in Java