Data Structures and Algorithms in Go - Heaps

hello today we'll be talking about heaps you'll be seeing a lot of animations in this video because i really think that visualizations can help you understand and remember concepts better and then after you learn the basic concepts you'll be able to write up a heap in code that can insert and extract data and we'll be doing that from scratch with very beginner friendly code in go i think heaps are a very interesting data structure because we think of it as a tree but it actually it's an array so i think it's interesting to see how it works especially when you're writing it up in code the heap data structure was originally introduced as a part of an algorithm called heapsort but the data structure that was introduced there was also useful for many other applications heaps are especially good for implementing priority queues uh in normal queues we take out the one that came in first right but in priority queues we take out the one with the highest priority which is where heaps can come in handy a heap is a data structure that can be expressed as a complete tree a complete tree means that all the levels in the tree are full except for the lowest level where some nodes can be empty but have all its node to the left we are looking at a binary heap here where the nodes have up to two children in the case for max heaps the largest key will be stored in the root and for all the nodes in the tree every parent will have a higher key than its children a max heap would be useful when we need to repeatedly remove a key that is the largest because we already know that the largest key is in the root this is a reason why getting the largest key can be so fast regardless of the size of the heap the opposite of the max heap is min heap where the root is the smallest key so in a min heap each parent node will have the smaller key than its children in this tutorial we're just going to be talking about max heaps because min heaps is just max heaps done opposite like we saw in the diagram so far heaps can be visualized as a tree but actually behind the scenes the keys are stored as an array where each node of the tree corresponds to an index of that array so strictly speaking heaps are actually just an array that operates like a tree this is possible because you can just easily calculate the indices of the children based on the parent's index and vice versa so with this simple formula we can get the index of the children for any index of the heap for example if we want to get the left child node index of index number 39 39 multiplied by 2 plus 1 will give us 79 which will be the index of the left child okay so now that we know the structure of heaps let's talk about the process of how we can insert keys in a heap whenever we do an insert we're going to add the new key at the bottom to the right of the tree in an array the bottom right node will be the last index after just mindlessly just placing the new node there we need to rearrange the nodes so that we can maintain the heap property which is to keep the parent key larger than its children we'll compare the new node to its parent node and swap it if the new node is higher we follow up the tree and keep on repeating this process until it gets to its place we call this process of rearranging the indices as heapify the heapify process is also needed after taking out an item of the tree so let's go and see how that works to extract the highest key in a heap we can just take out the root because we know that the root is the largest key after that we need to rearrange the node so that we can fill in the empty root while maintaining the heap property so first step right after losing the root we will fill the empty root with the last node so 34 which is the last key will go to the root position then we'll start the swapping process starting from the top look at these three nodes at the top just think out of the three who should be the parent like who should be on the top it should be 50 because 50 is the largest out of the three so 50 becomes the parent by swapping positions with 34. in other words the parent node 34 will be swapping places with its larger child the same goes for the next round 48 is the larger child so we will be comparing 34 to 48. um is 34 larger than 48 no so 34 doesn't deserve to stay there and it has to swap with 48. the time complexity of extracting and inserting a node in the heap would depend on the heapifying process simply adding an element at the end of the array or taking out a key from the first index of the array would not be the dominant part of the time complexity so we'll just ignore that part however the number of operations needed to heapify up or down would depend on how high the tree is so that's going to be the the one that affects the time complexity so we can express insert and extract as o of h where h means the height of the tree if we want to express the time complexity with n which would be the size of the array we can just replace h with log of n because the height and the number of indices have a logarithmic relation so the time complexity for uh inserting and extracting from a heap would be o of log n you can see that the heapifying process is the tricky part just adding and taking out an element is easy but rearranging the heap to maintain the heap property would be our main focus when we're doing the coding we'll be doing three main things first we need to make a struct that represents max heap then we're going to write an insert method and third we're going to write an extract method insert and extract will be accessible from the outside so insert and extract needs to start with the capital and also the struct max heap should also start with a capital as well so i'm just going to write them down here okay so this is going to be the big structure for what we're going to write now we're going to go and uh write down the struct for max heap and max heap is only going to contain just like one slice okay so it's actually it's actually a slice but i'm just going to call it array and then let's go to the the insert part so it's going to take in an integer which is the key to to add and we'll be doing two things here we're going to add the element to the array and then heapify so adding the element should be so we're just appending the the new key that was passed in um i'm going to append that to the array and then next we're going to rearrange it so that it can maintain the the heap properties this is the index of key because we appended it and this is going to be the last index and we didn't write this yet that's going to be our next step so it's going to take in an integer indicating where the heapify is going to start so inside the method we want to say swap when the current index is larger than the parent and to write that up we need to write some supporting functions and methods so we'll just write some functions that can help us convert the parent to the child indices and also we need a method that can actually um swap so this is to get the parent so the parent index can be expressed as index minus one divided by two the left child is always an odd number and the right child is always an even number so it's just going to round down and they're both going to indicate to the same parent index so this is going we're going to get the left child index and this is going to be the parent and we're going to return the left child index and also the same goes for the right and after that we also need a method that can swap the two values of our two indices uh in this case we actually have to modify the array and it's going to take in two indices and we're going to swap okay so right now we're swapping we're putting i2 into i1 and i1 into i2 and this expression this actually works in in go okay so now that we have these functions and methods we can finally start to write the max heapify method so when the parent is smaller than the current index so this is the key of the parent and this is a key of the current index and if the parent is smaller then we're going to swap and after we swap we're going to perform the same loop on the parent which is going to be the swapped swapped key so we need to update the loop so right now this part is swapping until it finds its place and this part is updating the current index to its parent indexed so that we can loop again we're not going to put an if statement um actually stopping the loop because if you look here when index gets to zero it's going to be impossible for this for condition to be satisfied because the parent and the parent index and the index are both going to be zero so the loop is just gonna stop so just for the sake of simplicity i'm just gonna leave it like this uh yeah there was a little mistake here sorry uh let's go to the main function now and test things out a little bit um here and i'm going to create a max heap so i'm going to call that just m just to check the struct that we built okay so you can see that inside the struct there is just one slice which we call array and that is currently empty right now and then we're going to add some uh keys and after each insert let's just um okay so we're going to run here uh first we're going to insert 10 so it's just inserting as a root because there was nothing there and after that we insert 20 but you can see 20 is first added at the end that is heapified and swap positions with 10 so that in the front it's always the the largest key at the front and after that we insert 30 and then we add it at the end and then you can see it's swapped with 20 so that it can be it's the biggest one so that it can be at the front at the root okay so we just did a simple test let's go and um do the next one which is extract so we have to return the item that we extracted so before we make any changes to the max heap let's just store it and just write the return part first so we're storing the first index in extracted and returning it and the rest of the process will write it between these two lines so we're going to get the last key the last index and put it in the root which would be the first index so this part over here is going to be the last index and we're putting that in index zero the first index okay and after we put the last index to the first index we have to make the slice shorter so that we can get rid of the last one i have to write the last index here which is already here i don't want to be repeating myself so i am going to write a variable declare a variable that is and then after that i'm going to put the max heapify down here we didn't write the max heapify down yet i'm going to write it in the next step but i'm just going to write and just one more step uh if i extract from an empty array it's going to panic so just to prevent that i'm gonna say if the length of the array is zero and then i'm just going to return uh that so if it meets a return it's just going to come out of the um the whole method okay inside this method we first need to get the larger child compare it to the current index and then swap it and we're going to repeat this loop until the index has no children so first let's write a full loop so imagine there is an index with only one child and that only child would be the last index because it's a nearly complete tree so if the left child index is the same as or smaller than the last index of the array we can say that this index has at least one child so here we want to say left child is same as or smaller than the last index child to compare is is going to be the child to compare with the index and to swap and now i can say um l which is left index is smaller or same as the last index so i'm going to make a for loop and first thing we need to do is to define the child to compare um when there is only one child or if the left child is larger we're going to assign the left child as child to compare so like this is the only child okay so for these two cases when the index is the oh sorry left child so when the left child is the only child or when the left child is larger than the right child we're going to put l as child to compare and in this case we're going to put r as child to compare okay so we put um l as child can compare for these two conditions and when the right child is larger i just put it else um that's going r is going to be child to compare just make sure to put this part at the first of the if statement because if this is true we don't want to be accessing the right child so because there's no right child and it's just going to cause a panic so just make sure you have this if this is actually true it's going to skip the rest okay so we've finished deciding the index for child to compare now let's go and compare and do the swapping so if the value of the array for index is smaller than child to compare then we're going to do the swapping so and after we swap we need to update variables in the loop so that the next round we will be doing this on the swapped index so this is when actually the index is smaller than the child to compare and we swap but if else if the value of the current index is actually larger than the larger child that means that it has found its right place so we will stop the whole heap heapify process and we're going to return like that okay so uh this is it uh let's go and test this out so we're going to go to the main method a main function sorry so i'm going to add a little bit more to the heap and then i'm going to go and extract five times so i need a full loop for that okay you just run the process and you can see that it's inserting and then starting from here we're going to be extracting and the largest key is always in the front so when we're doing the extracting i am actually going to go and see if we can put a break point and actually observe the swapping process so i'm going to go to max heapify down and whenever we have a swap i want to see it so i'm going to put a break point here then i'm going to go to debug and i'm going to debug it and it's a bit big i'm just going to make it a bit smaller so right now we stopped here so inside h this is the address and this is the actual heap and inside the heap there's an array and inside the array there are the keys before 30 was at the front but because we went through that process of putting um the last key to the front seven which was at the last has already come to the front and if we run again um 7 has exchanged its place with 20 because it doesn't deserve to belong there it's too small so it exchanged and then you can see that the index here is always going to follow the index of seven which is the the key that used to be at the back and run again and you see that 11 has swapped places with seven here run again so this time 10 has come forward and it already swapped places with 17 and then it's going to swap with 15 and then the next five came to the front and then it exchanged with 15 and it just goes on and on stop again with 13. okay so this is uh how you can observe the process of the swapping okay so uh that's it for today if you want to see more of my videos please subscribe to this channel i hope you had fun learning about heaps thank you so much for watching especially if uh to those who has been watching until the end um i'll see you on the next video thank you so much bye-bye

Channel: Junmin Lee

Views: 18,702

Keywords: data structures, golang, coding, programming, coding tutorial, programming tutorial, algorithms, computer science, software development, heaps in go, heaps in golang, heapify, binary heap, golang tutorial, golang tutorial for beginners, array, priority queue, priority queue in data structure, heapsort, linked lists, tries, binary search trees, stacks and queues

Id: 3DYIgTC4T1o

Length: 21min 43sec (1303 seconds)

Published: Sat Sep 26 2020