Java Program To Implement Min Heap
Chapter:
Data Structures
Last Updated:
13-07-2016 10:08:08 UTC
Program:
/* ............... START ............... */
public class JavaMinHeapExample {
private int[] Heap;
private int size;
private int maxsize;
private static final int FRONT = 1;
public JavaMinHeapExample(int maxsize) {
this.maxsize = maxsize;
this.size = 0;
Heap = new int[this.maxsize + 1];
Heap[0] = Integer.MIN_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 minHeapify(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));
minHeapify(leftChild(pos));
} else {
swap(pos, rightChild(pos));
minHeapify(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 minHeap() {
for (int pos = (size / 2); pos >= 1; pos--) {
minHeapify(pos);
}
}
public int remove() {
int popped = Heap[FRONT];
Heap[FRONT] = Heap[size--];
minHeapify(FRONT);
return popped;
}
public static void main(String... arg) {
System.out.println("The Min Heap is ");
JavaMinHeapExample minHeap = new JavaMinHeapExample(15);
minHeap.insert(5);
minHeap.insert(3);
minHeap.insert(17);
minHeap.insert(10);
minHeap.insert(84);
minHeap.insert(19);
minHeap.insert(6);
minHeap.insert(22);
minHeap.insert(9);
minHeap.minHeap();
minHeap.print();
System.out.println("The Min val is " + minHeap.remove());
}
}
/* ............... END ............... */
Output
The Min Heap is
PARENT : 3 LEFT CHILD : 5 RIGHT CHILD :6
PARENT : 5 LEFT CHILD : 9 RIGHT CHILD :84
PARENT : 6 LEFT CHILD : 19 RIGHT CHILD :17
PARENT : 9 LEFT CHILD : 22 RIGHT CHILD :10
The Min val is 3
Tags
Implement Min Heap, Java, Data Structures