Heaps data structures that are another form of trees. They are a special form of heaps and there are many types of heaps as well. We'll be talking about MaxBinaryHeap and MinBinaryHeap which similarly to a BST each parent can have a max of 2 children. The caveat for Max and Min heaps is that in a MaxBinaryHeaps, parent nodes are always larger than child nodes and you guessed it, in MinBinaryHeaps, parent nodes are always smaller than child nodes. Unlike a BST there is no order to left and right, the only principles that they follow (min/max) are what we just wrote about (parents smaller / larger than children). A binary heap is as compact as possible and all of the children of each node are as full as they can be and the left children are filled out before the right. One thing to mention here is that Binary Heaps are used to implement Priority Queues. So it would be a queue first in first out however depending on the priority/importance would determine when that node would be dequeued. They can also be used with graph traversal algorithms.
A heap can be represented as an array with some basic math. Think about it. You store indexed values and we know that the left is always filled out first so we can create some logic to find which values are children and parents. For any index of an array, which we'll call n, the left child is stored at 2n+1 and the right child is stored at 2n+2. With this logic we could build out a heap using a standard array, isn't that cool? We can also reverse this to get parent nodes from children. For a child at index n, its parent index would be floor((n-1)/2) and we'd have to add the floor method as there are not going to be decimal indices. Working with an array when we insert values, we push them onto then end and then we travel down the array until it reaches the point where it needs to "live".
When dealing with min/maxHeaps you generally have a method to extract either the min or max value which would be the root node. The way you do it remove the root node (shift()) and then replace the node with the very last element of the array. Then through a process known as "bubble-down" you would check the continue to check children nodes and if the new root is small than the child you swap until it is in its proper position. Again you'd want to start with the left side since we know in a heap the left children are filled out first. So the bubble down process is, well its just hard to grasp. I highly recommend watching some videos on it and console logging a whole bunch so you can see how it works. I still cannot quite explain it and when I say I barely understand it I think that might be the understatement of the day for sure.
We talked about priority queues just a bit at the beginning and I'll go over them very briefly. They are a data structure where each element has a priority and elements with a higher priority are served before elements with lower priorities. So this legitimately sounds like what we just did and the higher numbers in the maxBinaryHeap are actually the priorities. Thing about all values just being added to heap or end of the array. A newly high priority "case" would be added and whenever the next item was dequeued, you would swap the values and then bubble down to sit it at its proper spot. I am not 100% sure that was properly explained but I think you can get the idea. I never said I was a great writer and or teacher I'm just trying to get some knowledge to stick with me.
MaxBinaryHeap
MinBinaryHeap
Priority Queue
I feel like out of everything I've studied and "learned" thus far this one didn't stick near as much as the others. I feel like I may have rushed it and now definitely plan to revisit this very soon. But for now I keep on trucking and continue my journey.
Top comments (0)