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:
Hướng dẫn Java Design Pattern – Observer
Java Program to implement Priority Queue
Java Program to Implement Efficient O(log n) Fibonacci generator
Test a REST API with Java
Spring Boot - Interceptor
Concatenating Strings In Java
Java Program to Represent Graph Using Incidence List
Java Program to Find Nearest Neighbor for Dynamic Data Set
Intersection of Two Lists in Java
Java Program to Implement Min Hash
Request Method Not Supported (405) in Spring
Rest Web service: Filter và Interceptor với Jersey 2.x (P2)
Java Program to find the number of occurrences of a given number using Binary Search approach
Quick Guide to the Java StringTokenizer
Create Java Applet to Simulate Any Sorting Technique
Giới thiệu Java Service Provider Interface (SPI) – Tạo các ứng dụng Java dễ mở rộng
Java Program to Implement LinkedHashSet API
String Joiner trong Java 8
Java Program to Check for balanced parenthesis by using Stacks
Java Program to Use Dynamic Programming to Solve Approximate String Matching
Java InputStream to String
Java Program to Check Whether an Undirected Graph Contains a Eulerian Path
Build a REST API with Spring and Java Config
A Guide to System.exit()
Partition a List in Java
Java Program to Find the Vertex Connectivity of a Graph
Spring RestTemplate Request/Response Logging
Automatic Property Expansion with Spring Boot
Immutable Map Implementations in Java
Guide to the Java ArrayList
An Intro to Spring Cloud Vault
Java Program to Perform Searching Based on Locality of Reference