Heap and Tries
Introduction
Everything that I wrote here is based on my knowledge and therefore are unbounded by any copyright.
Heap
What is heap?
Heap is basically a data structure which implements the binary tree or to be precise, a complete binary tree to store it's data in a certain way. There are four kinds of heap :
1) Max Heap which always store the maximum value at it's root node and every parent node must has a greater or equal to it's child node value.
2) Min Heap which as opposed to Max Heap, will always store the minimum value at it's root node and every parent node must has a smaller or equal value to it's child node value.
3) Min-Max Heap which stores the minimum value at it's even level node and maximum value at it's odd level node.
4) Max-Min Heap which as opposed to Min-Max Heap, stores the maximum value at it's even level node and minimum value at it's even level node.
Insertion on a Heap data structure
Now, we need to keep in mind that heap data structure are often implemented using an array instead of a linked list.
Each node that is inserted on a heap data structure always get inserted at the first null index from the left of the array. Say a heap has a current size of 5 and because array index always start from 0, then we will insert the new node to index 5 as it is currently the first vacant node from the left.
After doing the insertion, we need to fix the heap data structure to avoid violating any of it's properties which I already mentioned here.
There are different ways to fix the properties of the heap depending on what type of heap are we dealing with. Here are the ways to fix the properties based on the type of heap which we will call as heapify :
- Max Heap Heapify
To fix the properties of the max heap, we will need to loop over the heap to clean out all the violations. To do it efficiently, we simply need to start from the last index of the heap (the last node that we inserted) by making a variable pointing to that last index. We will then compare the value that is stored in that variable index with it's parent. If it's parent is smaller than it, then we simply swap the value of those two indexes and change our variable to point to that parent index and loop that until the parent of the variable index is bigger than the value in the variable index.
-Min Heap Heapify
Fixing the properties of a min heap is basically the same as fixing the property of max heap, it's just that, instead of stopping the loop when the parent of the variable is bigger than the value stored in that variable index, we will stop the loop when the parent of the variable is smaller than the value stored in that variable index. And also we will only swap the parent and the variable nodes only if the parent is bigger or equal than the value in the variable index.
-Min-Max Heap Heapify
Things get a little more tricky when dealing with Min-Max or Max-Min Heap as there are a few things we need to keep in mind.
To fix the properties of a Min-Max Heap, first, we will do the same thing as what we did with min or max heap, we will create a variable pointing to that last index of the array that are not vacant. Next, we will want to compare the value of the variable index with it's parent node value. Remember that in a Min-Max Heap, the odd levels are always the maximum value and the even levels are always the minimum value and that the root of a Min-Max Heap will always have the smallest value of the heap. Therefore, after we compare it with it's parent node, if the parent node is at an odd level, then we will want to check whether the parent node is smaller than the variable. If it isn't then we can just stop the loop there as there will be no properties that are violated anymore. But if it is, then we need to swap the variable index content with it's parent's value. The opposite happen when the parent node is at an even level. Then we will have to check whether the parent node is bigger than the variable and do the same as before. If a swap happened, then the next thing we want to do is loop like before until there are no more violations that's happening. The only thing different is that this time, we will compare the variable with the grandparent of the variable.
-Max-Min Heap Heapify
Fixing the properties of the Max-Min Heap is just the same as Min-Max Heap, it just gets as in a Min-Max Heap, the even level are always the smallest value and the odd levels are always the biggest value. But this is not the case in a Max-Min Heap, it's the exact opposite.
Deletion in all type of heap data structure is the same except for the Min-Max and the Max-Min heap.
Here is how we delete the root node of a heap data structure :
-Max Heap or Min Heap
First, we will check if the heap has only one element in it. If it is then simply delete the root of that heap or if it is empty then just do nothing. But if there are more than one element in the heap, we will simply replace the root value with the value of the last index of the array and also delete that last index of the array. After that, we will simply do heapify to the new root using the method mentioned above and that will fix all of the violation in the heap.
-Min-Max Heap or Max-Min Heap
First, we will check if the heap has only one element in it. If it is then simply delete the root of that heap or if it is empty then just do nothing. But if there are more than one element in the heap, we will simply replace the root value with the value of the last index of the array and also delete that last index of the array. After that, we will compare the root node with all of it's grandchildren node and see if there are any violations. If there is any violation to the properties, then we will swap the root node with the most suitable node to replace the root position (in max-min case then swap the root with the biggest value of the grandchildren and do the opposite in case of a min-max heap). If there were any swapping that's done, then you will want to do heapify on that swapped node which isn't at the root node.
There are different ways to fix the properties of the heap depending on what type of heap are we dealing with. Here are the ways to fix the properties based on the type of heap which we will call as heapify :
- Max Heap Heapify
To fix the properties of the max heap, we will need to loop over the heap to clean out all the violations. To do it efficiently, we simply need to start from the last index of the heap (the last node that we inserted) by making a variable pointing to that last index. We will then compare the value that is stored in that variable index with it's parent. If it's parent is smaller than it, then we simply swap the value of those two indexes and change our variable to point to that parent index and loop that until the parent of the variable index is bigger than the value in the variable index.
-Min Heap Heapify
Fixing the properties of a min heap is basically the same as fixing the property of max heap, it's just that, instead of stopping the loop when the parent of the variable is bigger than the value stored in that variable index, we will stop the loop when the parent of the variable is smaller than the value stored in that variable index. And also we will only swap the parent and the variable nodes only if the parent is bigger or equal than the value in the variable index.
-Min-Max Heap Heapify
Things get a little more tricky when dealing with Min-Max or Max-Min Heap as there are a few things we need to keep in mind.
To fix the properties of a Min-Max Heap, first, we will do the same thing as what we did with min or max heap, we will create a variable pointing to that last index of the array that are not vacant. Next, we will want to compare the value of the variable index with it's parent node value. Remember that in a Min-Max Heap, the odd levels are always the maximum value and the even levels are always the minimum value and that the root of a Min-Max Heap will always have the smallest value of the heap. Therefore, after we compare it with it's parent node, if the parent node is at an odd level, then we will want to check whether the parent node is smaller than the variable. If it isn't then we can just stop the loop there as there will be no properties that are violated anymore. But if it is, then we need to swap the variable index content with it's parent's value. The opposite happen when the parent node is at an even level. Then we will have to check whether the parent node is bigger than the variable and do the same as before. If a swap happened, then the next thing we want to do is loop like before until there are no more violations that's happening. The only thing different is that this time, we will compare the variable with the grandparent of the variable.
-Max-Min Heap Heapify
Fixing the properties of the Max-Min Heap is just the same as Min-Max Heap, it just gets as in a Min-Max Heap, the even level are always the smallest value and the odd levels are always the biggest value. But this is not the case in a Max-Min Heap, it's the exact opposite.
Deletion in a Heap data structure
Deletion in all type of heap data structure is the same except for the Min-Max and the Max-Min heap.
Here is how we delete the root node of a heap data structure :
-Max Heap or Min Heap
First, we will check if the heap has only one element in it. If it is then simply delete the root of that heap or if it is empty then just do nothing. But if there are more than one element in the heap, we will simply replace the root value with the value of the last index of the array and also delete that last index of the array. After that, we will simply do heapify to the new root using the method mentioned above and that will fix all of the violation in the heap.
-Min-Max Heap or Max-Min Heap
First, we will check if the heap has only one element in it. If it is then simply delete the root of that heap or if it is empty then just do nothing. But if there are more than one element in the heap, we will simply replace the root value with the value of the last index of the array and also delete that last index of the array. After that, we will compare the root node with all of it's grandchildren node and see if there are any violations. If there is any violation to the properties, then we will swap the root node with the most suitable node to replace the root position (in max-min case then swap the root with the biggest value of the grandchildren and do the opposite in case of a min-max heap). If there were any swapping that's done, then you will want to do heapify on that swapped node which isn't at the root node.
Tries
What is tries?
Tries are basically a data structure which are basically a tree but with many branches and each node of the tree has only one data in it. A tries is used if you want to store a data and retrieve it in O(N) time complexity in the cost of high memory usage. A tries are usually implemented using a linked list but with the exception that the children of that node is stored with an array.
Say you want to store a string consisting of only lowercase alphabets. Then you would want to create as many children of a node as there are as many alphabets which you are going to use. Which are 26 (a-z).
Insertion in tries
Insertion in tries are pretty simple as you only need to insert each consecutive alphabets of a string to the tries by simultaneously iterating over the tries. For example, if you want to store the word "hello" and "help" in your tries. Then the program should iterate over the h alphabets first and store it at the children index of 'h'-'a' which will give an ascii value of the alphabets and then again iterating over the e alphabet and store it at the 'e'-'a' index of the 'h' node and loops that way until the end of the word which is the 'o' alphabet. In case we meet the end of the word, we will want to flag that node as the end of a word so that we know that o ends a certain word in the tries. After that we will move on to the word "help". Now we notice that the alphabet 'h' is already stored at the tries, therefore we will simply go to that 'h' node without storing it again. We do this each time we encounter an alphabet that is already stored in the tries. And same with before, we will mark the 'p' node as the end of the word in our program.
Deletion in tries
Deletion in tries are also pretty straight forward, but in order to not mess up the other word which are stored in the treis, we will need to do it in a bottom up manner as it will also make the code more efficeint.
First, we wil recursively go downward to the last alphabet of the string to be deleted and check if that node is the end of the string. If it is then we will first mark it again that it is no longer the end of a string. Then we will need to check if that node has any children. If it has then we will simply leave it be but if it doesn't have any then we will simply delete that node. And that way we will recursively go up the string's alphabet and if while going up the current node doesn't have any child and it's not the end of another word, we can simply delete it.
Searching in tries
Searching in tries is pretty simple as we will just have to iterate over each consecutive alphabet's node in the string we want to search and if we encounter a null while iterating or the last alphabet is not the end of a word, we will simply return false. Else, return true.
Here is a code in C programming language that I wrote myself:
Min-Heap :
Here is a code in C programming language that I wrote myself:
Min-Heap :
Tries :
Comments
Post a Comment