Heap (min)

 Heap

Heap is a data structure used to store numbers in form of binary tree i.e each node has two children.
Heap is the data structure behind PriorityQueue. Insert and pop operation inside a heap is oh log(n) complexity and can be used in multiple insert and pop operation questions. It is efficient and used in fastest sorting as well as sorting only takes nlog(n) complexity at worst case.

Important Functions for heap:

1. Heapify:

This function is a top down approach to set an given array into heap. The idea is to set the top priority Item at the parent node of given subtree of 3. We will compare priority of left item from parent and then from right item to that of winner of parent and left and then swap the top priority with parent item. If top priority wasn't the parent item then we call the heapify again for the right or left node with which the value was swapped. If we have a given array then we can run a loop into that array from bottom of tree to top (excluding leafs),i.e the loop will look like this for(int i = n/2 (n/2-1 for 0 based); i>=1 (i>=0 for 0 based);i++). We can call this function for every non leaf node (terminal child node) starting from bottom to create a heap. code for the same is below:

void heapify(int[] arr,int ind, int size){
int left=ind*2+1;
int right = ind*2+2;
int target = ind;
if(left<size && arr[left]<arr[ind]){
target = left;
}
if(right<size && arr[right]<arr[target]){
target = right;
}
if(target!=i){
swap(arr[target],arr[i]);
heapify(arr,target,size);
}
}

2. Insert:

This function is used to create heap from scratch or adding element to heap. The approach to adding element in the heap is to add the new element in the last (ind= heapsize+1) and get it heads node (ind/2), compare its priority with the head node, if it is of more priority then swap with head and make head as current node where the new item recides and repeat  the process in a bottoms up approach to set its correct position using while loop. Get the new elements head and check if head is smaller than new /current node then replace the head with current node and do the same with new head element  as current node. In other words this should be while head < current node. be carefull while getting head element in a 0 based indexing. head = (curr - 1)/2
code for the same is below:

void insert(int[] arr,int ele, int currsize, int maxsize){
if(currsize>=maxsize){
return;
}
arr[currsize++]=ele;
int currind = currsize-1;
int head =(curind-1)/2;
while(arr[head]>arr[curind]){
swap(arr[head],arr[curind])
curind=head;
head = (curind-1)/2;
}
}

3. Remove:

This function is used to pop from heap. The pop function removes the top element (minimum from min heap and maximum from max heap) which is the top priority element. The concept is to remove top element from the heap and put last element from heap to the top and use top down approach (heapify) to set the new top element into its correct position and update the heap. We need not run the loop this time as the rest of heap is fine, we just update positions of the new top element and call heapify with every swap until its in currect position, i.e either its a leaf or none of its child have higher priority.
code is below:

int remove(int[] arr,size){
if(size==0){
return -1;
}
int popedEle = arr[0];
arr[0] = arr[size-1];
size--;
heapify(arr,0,size);
}

Conclusion:

By this we conclude the heap data structure which is quite useful and easy.
we can implement without array also with few modifications. Adding n elements would cose nlog(n) operations and similarly popping n elements will cost nlog(n) operations. This is the worst case scenarios. This data structure can be used to perform heap sort. Create existing array as min heap and pop all elements and place them in a different array from the heap to get sorted array.

Comments

Popular posts from this blog

LeetCode 3Sum

New start Day 2 (1/10/2020) codeforces 492B Vanya and Lantern