Java Program To Implement Max Heap
Chapter:
Data Structures
Last Updated:
13-07-2016 10:12:39 UTC
Program:
/* ............... START ............... */
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());
}
}
/* ............... END ............... */
Output
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
Tags
Implement Max Heap, Java, Data Structures