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 Find Nearest Neighbor for Dynamic Data Set
Java Program to Solve the 0-1 Knapsack Problem
Dockerizing a Spring Boot Application
Java – InputStream to Reader
The Registration API becomes RESTful
Java Program to Find kth Largest Element in a Sequence
Apache Camel with Spring Boot
Java Program to Implement Branch and Bound Method to Perform a Combinatorial Search
Java Program to Implement Lloyd’s Algorithm
Java Program to Implement Circular Singly Linked List
Sorting in Java
Spring Cloud – Adding Angular
Java 8 Stream findFirst() vs. findAny()
Extract links from an HTML page
Shuffling Collections In Java
The Difference Between Collection.stream().forEach() and Collection.forEach()
Java Web Services – Jersey JAX-RS – REST và sử dụng REST API testing tools với Postman
HttpClient 4 – Send Custom Cookie
Java Program to Implement Warshall Algorithm
How to Break from Java Stream forEach
Java Program to Implement Ford–Fulkerson Algorithm
Giới thiệu về Stream API trong Java 8
Java Program to Implement Splay Tree
Adding Parameters to HttpClient Requests
A Guide to EnumMap
How to Delay Code Execution in Java
Spring Cloud AWS – EC2
Receive email using POP3
Java Program to Find Location of a Point Placed in Three Dimensions Using K-D Trees
Java Program to Perform Sorting Using B-Tree
An Intro to Spring Cloud Zookeeper
Spring Boot - Tomcat Port Number