Today we're going to discuss the binary heap data structure. In this episode, you'll learn where to use heaps in practice, how they can come handy to you during a coding interview, and how to implement them!
Along the way, we'll cover heap sort, priority queues, load balancing, and more!
Transcript
Episode 13 - Binary Heaps
00:00:02 - 00:05:01
welcome to the programming podcast. Here you can learn about computers in the brief and accessible way I'm your host mean could get hello everyone and this is also the programming podcast. We are going to discuss the binary heap data structure. Just like us your. We're going to start by introducing the structure and describing structure. We are going to try to imagine it because this way we'll be able to get a better understanding of how it works next to discuss the different operations that are efficient on top of binary heaps. And finally we're going to discuss a couple of practical use cases including purity cues which are also we're going to mention them regularly during the results and we're also going to mention keep sort which is sorting algorithm which as you can imagine uses heaps just like any other concept that we have described so far in the programming podcast binary heaps could be very valuable for you not only during golden kinch reviews but also in practice although Elsie. That's encoding interviews. They might be a little bit more calm compared to in practice birds well. It's good to know about their existence and is good to know when you can potentially apply them anyway so as you can imagine binary heaps are a binary data structure right in fact binary binary heaps are quite similar to binary trees with the main difference that they have one main constraints. The parents of two notes is always either bigger or smaller than its children. That's it we call the first type of heaps the wild way in which the parents always bigger and his children we call them Max. Heaps and the winds were the parent is always smaller than his children. We call him mini heaps for the sake of simplicity in this episode. We're going to focus all your hips but everything that we're going to discuss. It applies in both cases. Now let us try to imagine this data structure where every parents is smaller than its children. This way going from the leafs to the route we're eventually going to reach the smallest adamant in the binary heap so the roots of the binary heap is going to be the smallest element and in pretty much all binary trees. Were keeping a respirator. Direct reference to the rules of the tree which means that we have constant access to the smallest elements in our binary heap so we always maintain a direct reference was the smallest elements and we can always access it without performing any additional TRAVERSO. That is fantastic. That's why binary heaps are very frequently used for implementation of priority queues. What is a priority queue? Well in a priority queue. We are maintaining a collection of items order by their purity rights for example if we want to pick the least loaded server among a collection of servers we can pull them in a priority queue depending on the loads of each individual server. We can pose the least thought server on top of the period q while the server takes a request we can update his priority and find. It's right position in the Q. So that's the way we're going to take the next lease slow the server at the top of the pure to cure and so on and so forth. Now you might be thinking why should we even care about binary heaps can't we just use a simple array in this case we can just hear from the servers and every time when a certain server changes we can just sort dairy and just half the lease border always at the top rights should be quite simple. That's absolutely right. We can absolutely use this algorithm where we're sorting the servers depending on their lot. And this way we're going to half complexity and Logan because each comparison based sorting algorithm houses complexity at best now when we have to operate over several millions of server or several thousand server and who has to perform this sorting very frequently when given server as its `priority thinks may get tricky because soaking oldies servers with unloading complexity might not be very efficient. If we have several millions of server this multiplier at the beginning and can take a lot of time.
00:05:02 - 00:10:07
You might you think he will. We don't have to resort. We can just reorder array so once any of the server. Updates ITS PURITY. We can just find its position in this already sorted array and drop it there. That's great rights like we're dropping the complexity of this algorithm from end Logan to only end because we're iterating or the entire array until we eventually find the right position of the server. Whose loads capacity. We just changed. This is more efficient algorithm but is for sure not the most efficient Wanda to Kim us because we need to integrate over all these servers and for and this could be quite slow the awesome think about binary heaps is that we can drop the complexity of this operation for finding the right position of particular element from an to just log in and log in is a fascinating function because if we have ten million servers log 'em look of these ten million is going to be only about twenty three so imagine if we have ten servers who in we need to perform all the twenty three operations order to find the right position of certain server wants it updates. Its priority this way we can very efficiently. Keep track of the priorities of these individual elements in our priority queue and be able to efficiently provides element with highest priority right so as you can imagine binary heaps they support a couple of very common operations one of them. We already discussed taking the element and the top of the heap which has the mean value. Which has the minimum value in the entire collection for heaps and other operation is inserting an element and a third operation is extracting on adamant. We're going to discuss how we can add an element because it is a simple operation. But before that let us briefly discussed how can organize a binary heap What data structure we can use. In order to represent the usual way to implement binary heaves using an array now you might be thinking. You've got a razor fix is if we want to add more elements than Derek best where we can use the namic race. In this case we can just recites. You're a whilst we exceed its capacity does what's in most scenarios we do with binary heaps when implementing them with the race right but the second question is array. That's a Leonard Structure. How we're going to represent a three there. There is one really interesting trick that I want to tell you. About and district simplemente very conveniently a tree like structure with array without much trouble for every element and we can keep its children. It's two children at indexes two times and plus one and two times and plus two and that's it now let us think how we can implement insertion into such binary heap represented. Within the way we have our array. We're going to push the element that we want to insert as the end of the array and tries after that it is going to bubble up until it eventually reaches its correct position. How TO BUBBLE UP SO ONCE? We push the element at the end. It which is going to be a child of a particular parents in order to find the parents of the element just pushed. Gent. We're going to take its index and divided by two this way after round the results. Which means that we're going to just ignore the decimal part of division. We're going to find the parents element and we're going to compare the enemy just that we just inserted with the value associated with the parent index. That we just calculate if the element that just inserted is smaller rigging to swap with these two elements and. That's we have the guarantee that we can preserve the structure of the heap jobs because the parent that we just swapped with its child is already smaller than its other child so we can just put it as siblings. We're going to continue this process until we eventually reached the first adamant in our binary he which is the top of the heap or until we figure out that the current parents of the adamant that reinserting is already smaller right. So now we know about two different operations in the heat getting the maximum element or minimum adamant in many heaps and inserting adamant about deletion will not be able to cover in this episode but are strongly encourage.
00:10:07 - 00:12:26
Take a look at the resources associated with vitally he does. I have applied at podcast dot M. Dot com at the end. I want to spend some time discussing the different use cases for binary heaps. I remain. Tioned that we can use them for implementing pure accuse and purely accused their essential in the dextrous shortest path Algorithm when it comes down to finding a path in a graph usually binary heaps earn the most efficient way we can implement purely cue for dextrous algorithm. But they're a decent way so you can take advantage of them there. We can also use them for sorting numbers. So how are we going to sort a list of numbers by using a binary heap? Well Simple I. We're going to insert the elements in the heat. One by one which is going to cost us and logging operations right after that. We're going to extract the elements from the heap by one. We're always need to get the smallest element I for mean heaves or the biggest adamant I for Max keeps and this. Take another and logging operations because we have an numbers and if we want to extract the number is going to take us logan time so and multiplied by logging. That's how actually heap sort works. So see with one episode. We already covered heap sort. And Binary heaps pretty cool right. Finally I have also linked to really interesting paper which explains how we can implement a load balancing by using binary heaps right so this is what we covered binary heaps we discussed quite a few interesting things in fact we talked about when binary heaps reused who for example for implementing period juice. We discussed Haldi compare for deportation of Cues compared to erase. We also discussed a couple of practical use cases such as a DICK STRESS SHORTEST PATH ALGORITHM HEAP. Sort and load balancing really. Thank you very much for joining this episodes until next time learn about the episodes. You can follow me on twitter at Ham get you. That is the always ursus and recordings is available at podcast dot com get dot com. Thanks for listening.