This Java program is to implement max 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 max heap. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.
public class MaxHeap { private int[] Heap; private int size; private int maxsize; private static final int FRONT = 1; public MaxHeap(int maxsize) { this.maxsize = maxsize; this.size = 0; Heap = new int[this.maxsize + 1]; Heap[0] = Integer.MAX_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 maxHeapify(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)); maxHeapify(leftChild(pos)); }else { swap(pos, rightChild(pos)); maxHeapify(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 maxHeap() { for (int pos = (size / 2); pos >= 1; pos--) { maxHeapify(pos); } } public int remove() { int popped = Heap[FRONT]; Heap[FRONT] = Heap[size--]; maxHeapify(FRONT); return popped; } public static void main(String...arg) { System.out.println("The Max Heap is "); MaxHeap maxHeap = new MaxHeap(15); maxHeap.insert(5); maxHeap.insert(3); maxHeap.insert(17); maxHeap.insert(10); maxHeap.insert(84); maxHeap.insert(19); maxHeap.insert(6); maxHeap.insert(22); maxHeap.insert(9); maxHeap.maxHeap(); maxHeap.print(); System.out.println("The max val is " + maxHeap.remove()); } }
$javac MaxHeap.java $java MaxHeap The Max Heap is PARENT : 84 LEFT CHILD : 22 RIGHT CHILD :19 PARENT : 22 LEFT CHILD : 17 RIGHT CHILD :10 PARENT : 19 LEFT CHILD : 5 RIGHT CHILD :6 PARENT : 17 LEFT CHILD : 3 RIGHT CHILD :9 The max val is 84
Related posts:
Java Program to Implement Sorted Singly Linked List
Java Program to Implement the linear congruential generator for Pseudo Random Number Generation
Getting a File’s Mime Type in Java
Registration – Activate a New Account by Email
Java Program to Find Median of Elements where Elements are Stored in 2 Different Arrays
Spring Boot Gradle Plugin
Deploy a Spring Boot App to Azure
Java Program to Implement the Hungarian Algorithm for Bipartite Matching
Jackson – Unmarshall to Collection/Array
Spring MVC Tutorial
Annotation trong Java 8
Spring Security with Maven
Java Program to Implement Find all Forward Edges in a Graph
Java Program to Implement a Binary Search Tree using Linked Lists
Spring Cloud AWS – RDS
Java Program to implement Bi Directional Map
Đồng bộ hóa các luồng trong Java
The StackOverflowError in Java
Hướng dẫn Java Design Pattern – Flyweight
Java Program to Implement Find all Back Edges in a Graph
Assert an Exception is Thrown in JUnit 4 and 5
Java Program to Compute DFT Coefficients Directly
Java Program to Generate a Graph for a Given Fixed Degree Sequence
Redirect to Different Pages after Login with Spring Security
Java Program to Check Whether an Undirected Graph Contains a Eulerian Cycle
Java Program to Implement RoleList API
Java Switch Statement
How to Implement Caching using Adonis.js 5
Giới thiệu JDBC Connection Pool
Spring Boot - Google OAuth2 Sign-In
Spring WebClient and OAuth2 Support
Convert Character Array to String in Java