Uploads from Code Sketched

Currently Playing: Heaps tutorial | heap array implementation

In this heaps tutorial, we first get to know the basics around the heap data structure and then later dig into the concept of heap array implementation Notes download link: https://www.dropbox.com/s/5f827tewhyjlfm0/Heap%20sketch%20notes.pdf?dl=0 Other videos that you might like: 1. Learn about public-key cryptography https://www.youtube.com/watch?v=64DL9BNVwkU& 2. maximum substring in a string (Google interview question) https://www.youtube.com/watch?v=IHsX70r-fIQ 3. How the javascript engine works? https://www.youtube.com/watch?v=KM9coMpy5sQ 4. Real time median in a stream, another google interview question https://www.youtube.com/watch?v=1CxyVdA_654 5. Understand the Javascript event loop https://www.youtube.com/watch?v=XzXIMZMN9k4 6. Understand Promises in javascript https://www.youtube.com/watch?v=gV7SaMIFyg8 7. Git basics you must know https://www.youtube.com/watch?v=HDRXwokgWpo So let's go through our first sketch notes together which is about Heaps. Heaps are a tree based data structure meaning that they have a heirarchical relationship between the nodes similar to a tree. To be more specific, Heaps are binary & complete trees. What does that mean? They keyword binary means that each parent node will have at the max 2 children. The complete property means that the tree cannot have any empty nodes or spaces at any level other than the leaf nodes. So for example with respect to this tree, if we remove these 2 nodes, it's still a complete tree as the nodes are at the last level but if we remove this node as well, then this tree is no longer complete. That's about the competeness property but what makes a heap special? whats the property that makes a heap a heap? Its the heap property. It means that in a max heap, the value stored in the parent node is always greater that the value of the children node and this is true for all the nodes in the tree. Similarly, for a min heap, the value stored in the parent node is always smaller than the value of the children nodes and that's the speciality found only in heaps. But how does that help us programatically? Now that we know why heaps are important, let's move on to the next part of storing heaps in memory. Here's how we accomplish that. The 0th index stores the root node of the heap. and the children of every node can be calculated using this formula. To find the right child of the element at index n, we do 2(n) + 2 and to get the left child, we do 2(n) + 1. Taking an example here, the root is store at index 0. To get the left child, we do 2*0 + 1 that is 1. To get the right child, we do 2+0 + 2 that is 2. That's about fetching the parent, similar formulas exist for getting the parent of a particular node. To get the parent of an item at index n, we do n-1 /2 and take the floor of it. So for example here the ite, at index 9 which is 14, if we want to get to the parent, we do 9-½ = 8/2 that is 4. and thus the parent of 14 is 9 which is at the index 4 in the array. Now let's move onto how we can add elements to the heap. Adding an element to the heap always adds it to the end of the heap and then moves the element up to its proper position. Taking an example of this min heap, let's say we wanted to add the number 5 to this heap, we add it to the end of the heap and then exchange it with the parent until the parent is smaller that the element to keep the heap property of this min heap intact. Coming to the big o notation time complexity of the process of adding to the heap, we can see that it comes out to be log of n to the base 2. And that is understandable. Because once we add an element to the heap, we need to swap it on every level. But, as there are at the max order of log n levels in a binary tree, there can be at the max log of n swaps and thus the overall compelxity cannot exceed log n. In case of removing from the heap, the root is the one that gets removed always. Thus, as a rule, you can always remove the largest element from a max heap and the smallest element from a min heap. Once the root is removed leaving that slot empty, we take the last element from the heap, add it to the root and this time move it downwards until the heap property gets satisfied. That is, we keep swapping the element with the relevant children such that the min heap property of this min heap is maintained. Once a swap is no longer possible, the element is in its proper place. In case of addition, we can see swaps with the parent, and similarly in the case of removal, we see the swapping with children but the overall intent remain the same that is to maintain the heap property. Adding an element to the heap takes O(log(n)) and removal takes O(log(n)) as well. #heap #algorithms