Heap
What is Heap?
Heap is a complete binary tree. Complete means If we look at the tree there should not be void from left to right. Don’t be confused that there should be children for every node. What I am trying to say is that if there exists any left uncle (left parent) for a child then that uncle must have children. However, the right uncle may /maynot have children. Or in short, at every level there should not be void while traversing from left to right. For any child it’s predecessor must be filled.
- Heap is an abstract data type as the underlying data structure for heap is an array.
- Heap is of two type: i) Max Heap ii) Min Heap
- Max heap: In max heap, each parent node’s value or key is greater than its children. Important thing here to note is that we don’t need to bother about leftChild or rightChild as in the case of Binary Search Tree we have rightChild > leftChild. But here any node between leftChild and rightChild can be greater. But whatever be the scenario, parentNode is always greater than childrenNode.
- Min heap: In mean heap, each parent node’s value or key is smaller than its children. Important thing here to note is that we don’t need to bother about leftChild or rightChild as in the case of Binary Search Tree we have rightChild > leftChild. But here any node between leftChild and rightChild can be greater. But whatever be the scenario parentNode is always smaller than the childrenNode.
Time and Space Complexity:
- Space complexity = O(n)
- Time complexity to build a heap = O(n) + O(logn) = O(n).
- Time complexity to get Max element from max heap = O(1)
- Time complexity to get Min element from min heap = O(1)
- Time complexity to remove an element from root = O(1) + O(logn) = O(logn)
- Time complexity to remove any element except root = O(n) + O(logn) = O(n)
- Time complexity for Heapsort = O(nlogn)
Insertion:
We can insert any element into heap in O(1) as the underlying data structure for heap is an array. And array indexes can be accessed in O(1). But then after inserting we have to check the heap property. We call that operation heapify. So it’s going to visit the height of the tree. So time complexity for visiting a complete binary tree is going to take O(logn). Therefore, Inserting an element into the heap is going to take O(logn) time.
Deletion:
Generally we are interested in deleting the root element from the heap. Because heap is most of the time used as auxiliary data structure for graph related algorithms such as shortest path algorithms. We can take out the root element in O(1), but it’s going to create a void at that place. So to delete the root element we first store the root element into a temp variable then we put the last leaf node at root and decrease the size by 1 then apply heapify. As we know heapify takes O(logn). So, Deleting a root element from the heap is going to take O(logn) + O(1) = O(logn).
i) Heap.java
class Heap {
private Integer[] heap;
private int currentPosition = -1;
private String type;
public Heap(int size,String type){
this.heap = new Integer[size];
this.type = type;
}
public void insert(int data){
if(isFull()){
throw new RuntimeException("Heap is Full.");
}
this.heap[++currentPosition] = data;
fixUp(currentPosition);
}
public void fixUp(int pos){
if(pos == 0){
return;
}
int parent = (pos-1)/2 ;
if(type == "MAX"){
if(this.heap[parent] < this.heap[pos]){
int temp = heap[parent];
this.heap[parent] = this.heap[pos];
this.heap[pos] = temp;
fixUp(parent);
}
}else if(type == "MIN"){
if(this.heap[parent] > this.heap[pos]){
int temp = heap[parent];
this.heap[parent] = this.heap[pos];
this.heap[pos] = temp;
fixUp(parent);
}
}
}
public int getRoot(){
return this.heap[0];
}
public int getMax() {
int res = this.heap[0];
this.heap[0] = this.heap[currentPosition];
this.heap[currentPosition--] = null;
fixDown(0);
return res;
}
private void fixDown(int index){
if(index >= this.currentPosition){
return;
}
int leftChild = 2*index + 1;
int rightChild = 2*index + 2;
if(rightChild>currentPosition){
if(leftChild>currentPosition){
return;
}else{
int max = leftChild;
// if(this.heap[leftChild]{
// max = rightChild;
// }
if(this.heap[max]>this.heap[index]){
int temp = this.heap[leftChild];
this.heap[max] = this.heap[index];
this.heap[index] = temp;
index = max;
fixDown(index);
}
}
}
else{
int max = leftChild;
if(this.heap[leftChild]{
max = rightChild;
}
if(this.heap[max]>this.heap[index]){
int temp = this.heap[max];
this.heap[max] = this.heap[index];
this.heap[index] = temp;
index = max;
fixDown(index);
}
}
}
public void heapsort() {
while(this.currentPosition>=0){
int temp = this.heap[0];
System.out.print(temp+" ");
this.heap[0] = this.heap[currentPosition--];
fixDown(0);
}
}
private boolean isFull(){
return this.currentPosition == this.heap.length;
}
public void getHeap(){
for (int i =0;i<=this.currentPosition;i++)
System.out.print(heap[i]+" ");
>
}
ii) Main.java
public class Main
{
public static void main(String[] args) {
String type = "MAX"; // For min type = "MIN"
Heap h = new Heap(10,type);
h.insert(20);
h.insert(5);
h.insert(10);
h.insert(15);
h.insert(13);
h.insert(25);
h.insert(30);
h.insert(100);
h.insert(50);
h.insert(200);
h.getHeap();
System.out.println();
System.out.print("Root: "+h.getMax());
System.out.println();
h.getHeap();
System.out.println();
h.heapsort();
}
}