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:
A Guide to HashSet in Java
The HttpMediaTypeNotAcceptableException in Spring MVC
Spring Boot - Enabling HTTPS
Performance Difference Between save() and saveAll() in Spring Data
Java Program to Find the Mode in a Data Set
Partition a List in Java
HTTP Authentification and CGI/Servlet
Using Optional with Jackson
Java Program to Check Cycle in a Graph using Topological Sort
Giới thiệu Google Guice – Injection, Scope
Java Program to Implement a Binary Search Tree using Linked Lists
Java Program to Check whether Undirected Graph is Connected using DFS
Java Program to Use Above Below Primitive to Test Whether Two Lines Intersect
Entity To DTO Conversion for a Spring REST API
Refactoring Design Pattern với tính năng mới trong Java 8
Registration – Password Strength and Rules
Java – Rename or Move a File
Java Program to Implement Counting Sort
Initialize a HashMap in Java
Hướng dẫn Java Design Pattern – Composite
Java Program to Solve a Matching Problem for a Given Specific Case
Java Program to Implement JobStateReasons API
Handling Errors in Spring WebFlux
Java Program to Implement Stack API
Lớp lồng nhau trong java (Java inner class)
More Jackson Annotations
Java Program to Implement Knapsack Algorithm
Java Program to Implement Expression Tree
Java Program to Implement Extended Euclid Algorithm
Queue và PriorityQueue trong Java
HttpClient Basic Authentication
Java Program to Implement ArrayDeque API