Need Programming Assignment Help?

Get Help with Programming Assignment in Java, C/C++, Dot Net, PHP, Database and UML Diagrams

Java Program to Implement Max Heap

Java Program to Implement Max Heap

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

public class JavaMaxHeapExample {

 private int[] Heap;
 private int size;
 private int maxsize;

 private static final int FRONT = 1;

 public JavaMaxHeapExample(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 ");
 JavaMaxHeapExample maxHeap = new JavaMaxHeapExample(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());
 }
}