Min Heap and Max Heap in Java.
In this post we will see what is Min Heap, Max Heap, the operation it supports and the time and space complexity of each operation.
Complete Binary Tree.
Min Heap and Max Heap uses the concept of Complete Binary Tree.
Min-heap: the value of each node is greater than or equal to the value of its parent, that is the element with minimum value is always at the root.
Max-heap: the value of each node is less than or equal to the value of its parent, that is the element with maximum value is always at the root.
If we represent the array as Complete Binary tree, how is left child and right child index calculated?
Check this link which explains heap concepts in detail Heap Sort Algorithm
In this post, we will implement Min Heap and the operation it support would be,
- add - this will add a element to a heap
- remove - this will remove a element from a heap
- peek - this will give you a minimum element in a heap
Time complexity of each operation,
- add - O(log n)
- remove - O(log n)
- peek - O(1)
Since in addition/removal, new element added/removed could disturb the heap property so we have to scan all the elements belonging to height of binary tree which take Log n operation.
Min Heap in Java
package javabypatel.heap;
public class MinHeap {
private int[] heap;
private int size;
private int currentIndex=-1;
public MinHeap(int size) {
this.heap = new int[size];
this.size = size;
}
public int remove() {
if (currentIndex < 0) {
throw new RuntimeException("Heap is empty");
}
int temp = heap[0];
heap[0] = heap[currentIndex];
currentIndex--;
bubbleDown(0);
return temp;
}
public int peek() {
if (currentIndex < 0) {
throw new RuntimeException("Heap is empty");
}
return heap[0];
}
public void add(int data) {
if ((currentIndex + 1) >= size) {
throw new RuntimeException("Heap full");
}
heap[++currentIndex] = data;
bubbleUp(currentIndex);
}
private int getLeftChildIndex(int index) {
return index * 2 + 1;
}
private int getRightChildIndex(int index) {
return index * 2 + 2;
}
private int getParentIndex(int index) {
return (index - 1) / 2;
}
private boolean isParentPresent(int index) {
return getParentIndex(index) >= 0;
}
private void bubbleUp(int index) {
if (!isParentPresent(index)) {
return;
}
int parentIndex = getParentIndex(index);
if (heap[index] < heap[parentIndex]) {
swap(index, parentIndex);
bubbleUp(parentIndex);
}
}
private void bubbleDown(int index) {
int left = getLeftChildIndex(index);
int right = getRightChildIndex(index);
int minIndex = index;
if (left <= currentIndex && heap[left] < heap[minIndex]) {
minIndex = left;
}
if (right <= currentIndex && heap[right] < heap[minIndex]) {
minIndex = right;
}
if (index != minIndex) {
swap(index, minIndex);
bubbleDown(minIndex);
}
}
private void swap(int index1, int index2) {
int temp = heap[index1];
heap[index1] = heap[index2];
heap[index2] = temp;
}
}
package javabypatel.heap;
public class MinHeapMain {
public static void main(String[] args) {
MinHeap minHeap = new MinHeap(10);
minHeap.add(5);
minHeap.add(1);
System.out.println(minHeap.peek());
minHeap.remove();
minHeap.add(4);
System.out.println(minHeap.peek());
minHeap.add(2);
System.out.println(minHeap.peek());
}
}
Output: 1
4
2
Max Heap is very similar to Min Heap, except we keep the maximum at the top.
Max Heap in Java
package javabypatel.heap;
public class MaxHeap {
private int[] heap;
private int size;
private int currentIndex=-1;
public MaxHeap(int size) {
this.heap = new int[size];
this.size = size;
}
public int remove() {
if (currentIndex < 0) {
throw new RuntimeException("Heap is empty");
}
int temp = heap[0];
heap[0] = heap[currentIndex];
currentIndex--;
bubbleDown(0);
return temp;
}
public int peek() {
if (currentIndex < 0) {
throw new RuntimeException("Heap is empty");
}
return heap[0];
}
public void add(int data) {
if ((currentIndex + 1) >= size) {
throw new RuntimeException("Heap full");
}
heap[++currentIndex] = data;
bubbleUp(currentIndex);
}
private int getLeftChildIndex(int index) {
return index * 2 + 1;
}
private int getRightChildIndex(int index) {
return index * 2 + 2;
}
private int getParentIndex(int index) {
return (index - 1) / 2;
}
private boolean isParentPresent(int index) {
return getParentIndex(index) >= 0;
}
private void bubbleUp(int index) {
if (!isParentPresent(index)) {
return;
}
int parentIndex = getParentIndex(index);
if (heap[index] > heap[parentIndex]) {
swap(index, parentIndex);
bubbleUp(parentIndex);
}
}
private void bubbleDown(int index) {
int left = getLeftChildIndex(index);
int right = getRightChildIndex(index);
int minIndex = index;
if (left <= currentIndex && heap[left] > heap[minIndex]) {
minIndex = left;
}
if (right <= currentIndex && heap[right] > heap[minIndex]) {
minIndex = right;
}
if (index != minIndex) {
swap(index, minIndex);
bubbleDown(minIndex);
}
}
private void swap(int index1, int index2) {
int temp = heap[index1];
heap[index1] = heap[index2];
heap[index2] = temp;
}
}
package javabypatel.heap;
public class MaxHeapMain {
public static void main(String[] args) {
MaxHeap maxHeap = new MaxHeap(10);
maxHeap.add(5);
maxHeap.add(1);
System.out.println(maxHeap.peek());
maxHeap.remove();
System.out.println(maxHeap.peek());
maxHeap.add(15);
System.out.println(maxHeap.peek());
maxHeap.add(20);
System.out.println(maxHeap.peek());
}
}
Output: 5
1
15
20
You may also like to see
Advanced Java Multithreading Interview Questions & Answers
Type Casting Interview Questions and Answers In Java?
Exception Handling Interview Question-Answer
Method Overloading - Method Hiding Interview Question-Answer
How is ambiguous overloaded method call resolved in java?
Method Overriding rules in Java
Interface interview questions and answers in Java
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
No comments:
Post a Comment