Okay lets implement MinHeap and MaxHeap ☠️ First, What is a Heap? 🤔 Heap (Binary Heap) is a binary tree where all levels must be completely filled except for the last level, which can be partially filled. The nodes in the last level must be filled from left to right without any gaps. For example:
10
/ \
20 15
/ \ / \
30 40 50
the above is a Valid Binary Heap, the below is NOT:
10
/ \
20 15
/ \ \
30 40 50 <-- This is invalid ❌
Hope you got it. Now you lets understand what is MinHeap and MaxHeap. Simple! They are just two special kind of Heaps where There is a special relationship between a parent and the children or child if its a single "Ladla". The relationship is : MinHeap: The parent will be always smaller than the children. MaxHeap: The reverse. The parent will be always bigger than the children.
Now because of this if you consider any subtree the root of that subtree will be smalest in case of MinHeap and biggest in case of MaxHeap. That means if you want the minimum element in O(1) time you can use a MinHeap to store your data and similarly for maximum element you can use MaxHeap.
MinHeap example:
10
/ \
20 15
/ \ / \
30 40 50
MaxHeap example:
50
/ \
20 15
/ \ / \
10 5 12
Now we are going to build a MaxHeap and MinHeap datastructres with all the neccessary methods:
insert -> inserts a value to the heap
peek -> Returns the Max or Min element (ie root) depending on the Heap without deletion.
poll -> Deletes and returns the Max or Min element (ie root)
isEmpty -> Checks if heap is empty or not
isFull -> Checks if heap is full or not
insert: The element is always inserted at the bottom of the tree. After which the heap is corrected if it violates the Min heap or Max heap property. For that the function swim() is used. swim: This function corrects the heap from bottom to top. It checks if the current child is smaller or larger than the parent and accordingly it swaps the parent with child. Then it repeats the process to the above subtree. poll: This function deletes the root node and replace it with the last node of the heap. After this the heap needs to corrected if the property is violated. For this sink() method is used. sink: This method checks if both the children (or child if LADLA) is smaller or greater than the parent or not according to the min/max heap implementaion. And accordingly it swaps the parent with the child. If both are smaller or greater, it can take any one to swap with.
Ok enough explaination, let's write some code! In the code we will use an array to store the heap. We will use Java to implement this. And we will use Generics.
MinHeap:
import java.lang.reflect.Array;
/**
* A generic Min heap implementation for storing and managing Numbers
* @param <T> Type of numeric element to be stored in the heap (eg: Integer, Float, Double)
*/
public class MinHeap<T extends Comparable<T>> {
private T[] arr; // The array used to store the heap elements
private int size; // The current number of elements in the heap.
/**
* Constructor to initialize the MinHeap with a specific size.
*
* @param clazz The class type of the numeric elements (eg: Integer, Float, Double)
* @param capacity The maximum number of elements the heap can hold
*/
public MinHeap(Class<T> clazz, int capacity){
this.arr = (T[]) Array.newInstance(clazz, capacity);
this.size = 0;
}
/**
* Gets the curent size of the heap
* @return The current size of the heap
*/
public int getSize(){
return this.size;
}
/**
* Get the capacity of the heap
* @return The capacity of the heap
*/
public int getCapacity(){
return this.arr.length;
}
/**
* Get the index of the parent node for a given node's index
* @param i The index of the child node
* @return The index of the parent node
*/
private int getParentIndex(int i){
return (int) Math.floor((i - 1) / 2);
}
/**
* Restores the MinHeap property by swiming up from bottom to top
* This is called when a new element is added to the heap and the MinHeap property is violated
*/
private void swim(){
int i = this.size - 1;
// loop until we reach the root element or heap is correct
while(i != 0){
T parentElement = this.arr[this.getParentIndex(i)];
T childElement = this.arr[i];
if(parentElement.compareTo(childElement) > 0){
// parent is greater than child which violates Min heap property, so swap them
this.swap(this.getParentIndex(i), i);
i = this.getParentIndex(i); // now point to the parent to repeat the same upstream
continue;
}
break;
}
}
/**
* Restores the MinHeap property by sinking down from top (root) to bottom
* This is called after removing the root (minimum element) from the Heap and replacing it with the last element from the Heap
*/
private void sink(){
// sink from top to bottom after deletion of the root element and replacing with the last element from the heap
int i = 0;
while(true){
int leftIndex = 2 * i + 1;
int rightIndex = 2 * i + 2;
if(leftIndex >= size) break; // no children, stop sinking
T parentElement = this.arr[i];
T leftChildElement = this.arr[leftIndex];
T rightChildElement = rightIndex < size ? this.arr[rightIndex] : null;
T smallestChildElement = leftChildElement;
int smallestChildIndex = leftIndex;
if(rightIndex < size && rightChildElement.compareTo(leftChildElement) < 0){
smallestChildElement = rightChildElement;
smallestChildIndex = rightIndex;
}
if(parentElement.compareTo(smallestChildElement) > 0){
this.swap(i, smallestChildIndex);
i = smallestChildIndex;
continue;
}
break;
}
}
/**
* Inserts an element to the Min heap
* @param element the element to be inserted
*/
public void insert(T element) throws Exception{
if(this.isFull()){
throw new Exception("Maximum capacity of the heap reached");
}
this.arr[this.size] = element;
this.size++;
this.swim();
}
/**
* Get the minimum element (ie root) of the MinHeap
* @return the minimum element
*/
public T peek(){
if(this.isEmpty()){
return null;
}
return this.arr[0];
}
/**
* Delete and return the minimum element (ie root element) from the MinHeap
* @return the deleted minimum element
*/
public T poll(){
if(this.isEmpty()){
return null;
}
T root = this.arr[0];
this.arr[0] = this.arr[this.size - 1];
if(this.size == 1){
this.arr[0] = null;
}
this.sink();
this.size--;
return root;
}
/**
* Checks if the MinHeap is empty
* @return true if heap is empty else false
*/
public boolean isEmpty(){
return this.size == 0;
}
/**
* Checks if the heap is full or not
* @return true if the heap is full else false
*/
public boolean isFull(){
return this.size == this.arr.length;
}
/**
* Swap the i, j element with each other in the heap array
* @param i the index of one of the node to be swaped
* @param j the index of the other node to be swaped with
*/
private void swap(int i, int j){
T temp = this.arr[i];
this.arr[i] = this.arr[j];
this.arr[j] = temp;
}
/**
* Additional methods to be implemented:
* - deleteMin(): To remove and return the minimum element (root) from the heap.
* - isEmpty(): To check if the heap is empty.
*/
public static void main(String[] args) {
MinHeap<Integer> minHeap = new MinHeap<>(Integer.class, 10);
try {
minHeap.insert(5);
minHeap.insert(4);
minHeap.insert(7);
} catch (Exception e) {
System.err.println(e);
}
System.out.println(minHeap.poll()); // should return 4
System.out.println(minHeap.peek()); // should return 5
}
}
Maxheap implementation is pretty much same, the only difference is with the comparision part and the sink method. MaxHeap:
import java.lang.reflect.Array;
/**
* A generic Min heap implementation for storing and managing Numbers
* @param <T> Type of numeric element to be stored in the heap (eg: Integer, Float, Double)
*/
public class MaxHeap<T extends Comparable<T>> {
private T[] arr; // The array used to store the heap elements
private int size; // The current number of elements in the heap.
/**
* Constructor to initialize the MaxHeap with a specific size.
*
* @param clazz The class type of the numeric elements (eg: Integer, Float, Double)
* @param capacity The maximum number of elements the heap can hold
*/
public MaxHeap(Class<T> clazz, int capacity){
this.arr = (T[]) Array.newInstance(clazz, capacity);
this.size = 0;
}
/**
* Gets the curent size of the heap
* @return The current size of the heap
*/
public int getSize(){
return this.size;
}
/**
* Get the capacity of the heap
* @return The capacity of the heap
*/
public int getCapacity(){
return this.arr.length;
}
/**
* Get the index of the parent node for a given node's index
* @param i The index of the child node
* @return The index of the parent node
*/
private int getParentIndex(int i){
return (int) Math.floor((i - 1) / 2);
}
/**
* Restores the MaxHeap property by swiming up from bottom to top
* This is called when a new element is added to the heap and the MaxHeap property is violated
*/
private void swim(){
int i = this.size - 1;
// loop until we reach the root element or heap is correct
while(i != 0){
T parentElement = this.arr[this.getParentIndex(i)];
T childElement = this.arr[i];
if(parentElement.compareTo(childElement) < 0){
// parent is greater than child which violates Min heap property, so swap them
this.swap(this.getParentIndex(i), i);
i = this.getParentIndex(i); // now point to the parent to repeat the same upstream
continue;
}
break;
}
}
/**
* Restores the MaxHeap property by sinking down from top (root) to bottom
* This is called after removing the root (minimum element) from the Heap and replacing it with the last element from the Heap
*/
private void sink(){
// sink from top to bottom after deletion of the root element and replacing with the last element from the heap
int i = 0;
while(true){
int leftIndex = 2 * i + 1;
int rightIndex = 2 * i + 2;
if(leftIndex >= size) break; // no children, stop sinking
T parentElement = this.arr[i];
T leftChildElement = this.arr[leftIndex];
T rightChildElement = rightIndex < size ? this.arr[rightIndex] : null;
T smallestChildElement = leftChildElement;
int smallestChildIndex = leftIndex;
if(rightIndex < size && rightChildElement.compareTo(leftChildElement) > 0){
smallestChildElement = rightChildElement;
smallestChildIndex = rightIndex;
}
if(parentElement.compareTo(smallestChildElement) < 0){
this.swap(i, smallestChildIndex);
i = smallestChildIndex;
continue;
}
break;
}
}
/**
* Inserts an element to the Min heap
* @param element the element to be inserted
*/
public void insert(T element) throws Exception{
if(this.isFull()){
throw new Exception("Maximum capacity of the heap reached");
}
this.arr[this.size] = element;
this.size++;
this.swim();
}
/**
* Get the minimum element (ie root) of the MaxHeap
* @return the minimum element
*/
public T peek(){
if(this.isEmpty()){
return null;
}
return this.arr[0];
}
/**
* Delete and return the minimum element (ie root element) from the MaxHeap
* @return the deleted minimum element
*/
public T poll(){
if(this.isEmpty()){
return null;
}
T root = this.arr[0];
this.arr[0] = this.arr[this.size - 1];
if(this.size == 1){
this.arr[0] = null;
}
this.sink();
this.size--;
return root;
}
/**
* Checks if the MaxHeap is empty
* @return true if heap is empty else false
*/
public boolean isEmpty(){
return this.size == 0;
}
/**
* Checks if the heap is full or not
* @return true if the heap is full else false
*/
public boolean isFull(){
return this.size == this.arr.length;
}
/**
* Swap the i, j element with each other in the heap array
* @param i the index of one of the node to be swaped
* @param j the index of the other node to be swaped with
*/
private void swap(int i, int j){
T temp = this.arr[i];
this.arr[i] = this.arr[j];
this.arr[j] = temp;
}
public static void main(String[] args) {
MaxHeap<Integer> MaxHeap = new MaxHeap<>(Integer.class, 10);
try {
MaxHeap.insert(5);
MaxHeap.insert(4);
MaxHeap.insert(7);
} catch (Exception e) {
System.err.println(e);
}
System.out.println(MaxHeap.poll()); // should return 7
System.out.println(MaxHeap.peek()); // should return 5
}
}
Hope it helps! You can use this classes as utility class in anyof your project.