What Is a Binary Heap?

binary heaps are especially useful data structures used in a variety of contexts but why would we want to use one how do they work and what problems do they solve to answer these questions let's start with a problem let's say you have some tasks to complete and each task has a priority some number representing the tasks importance one for your most important tasks two for the next tier of importance and so forth you want to organize tasks such that you can easily access your most important tasks first this way of organizing data is called a priority queue a collection of values where at any time we always want access to the most important item how would you store this data in a data structure you could use an array sorted by priority that makes it pretty quick to access high-priority items but with a fixed size array you'll run into trouble if you ever need to add a new element into your priority queue there's no space for another item another option is a linked list with each node of data pointing to the node that follows it this strategy makes it possible to add new data by rearranging those pointers but it's still not so efficient to add new data we might have to look through the entire linked list just to find the right place to add our new information this is where binary heaps come in binary heaps also consist of nodes of data but they're structured as a binary tree that means instead of each node of pointing to a single other node nodes can have up to two so-called child nodes a left child and a right child a node is allowed to have no children just a left child or both a left and right child each node in a binary heap also obeys an invariant in other words a property that will always be true in a binary heap and in particular a type of binary heap called a min the value of any node must be less than or equal to the values of its child nodes why is that important well this means the node with the smallest value must be at the top or root of this tree so with this structure it's easy to find the minimum value node just by looking at the root of the tree and ignoring everything else within this binary heap there are two common operations will likely need to perform the first is insertion adding a new node to the heap as we might do if we have some new task to complete for example the second is deletion removing whatever is at the root of the heap as we might do if we've completed the highest priority task so let's start with insertion when we want to add a new value to a binary heap there are two factors we'll need to bear in mind first what the shape of the new heap will be and second preserving the heap invariant that nodes are never greater than their children before we think about the heap invariant let's ignore the actual values associated with these nodes for now and just think about the shape of our heap remember that each node can have a left child and a right child ideally we want the left and right sides to be balanced with an equal number of nodes on each side of each node since if the heap is imbalanced it might be a less efficient to work with but depending on if there are an even or odd number of nodes in the heap it might not always be possible for the heap to be perfectly balanced to account for that we will allow nodes you have one extra node in the left subtree then in the right subtree this gives us a pattern for what the shape of every different sized binary heap should look like with one node it's just the root the second node we add to the left side the third node goes to the right to keep things balanced the fourth node needs to be the left most node since we add to the left first before we add to the right the fifth node must be the child of the third node to keep things balanced again the sixth and seventh nodes then fill in the last blanks in this level left first and then right the eighth node would then be the left most node of a new level of this tree and so forth whenever we add new nodes to the heap we need to preserve this kind of shape but if we just take any new element and add it to the bottom of the heap in the right place the heap invariant will often be broken the parent might be greater than the new node for example so will likely need to make some adjustments to this heap to ensure that it follows the heap invariant we'll do so by repeatedly applying a rule compare the node we've just added to the parent if the parent is greater than the node which isn't allowed in a binary heap then we need to swap the node with its pen once we make that swap will you repeat the process if the parent is greater than the node then we swap the two once we've reached a point where the parent is no longer greater than the child we can stop the heap invariant is now satisfied in the worst case we might add a node that's smaller than every other node in the heap and in that case we would need to make swaps all the way to the top of the heap but often that won't be necessary and we'll just need to make a few swaps before the node ends up in the right place we now have the ability to add a node to the heap the other action we'll want to perform is deleting a node from the binary heap because the binary heap is designed to just give us access to the minimum element that's the only one were allowed to delete but once we remove the node from the heap we're left with a heap that isn't in the correct shape anymore in particular it's missing a root node so how do we fix the problem as we did with insertion let's first get the heap in the correct shape and then worry about satisfying the heap in Berrien that elements can't be greater than their children to get the heap into the correct shape we can take an element from the bottom layer of the heap and move it to be the new root remember that we need to preserve the rules for the shape so if there's unevenness on the bottom layer we should remove a node such that we balance the heap and if it's already even we should remove from the right side first before we remove from the left of course once we move the last element to the root of the heap the heap invariant will likely not be satisfied anymore the new root is probably going to be greater than its children so now we need to repair the heap similarly to how we did so with insertion when we were inserting into the heap we made swaps starting at the bottom and moving upwards now we'll make swaps starting at the top and moving downwards if the node is less than or equal to both of its children were done and we don't need to make any more swaps but otherwise we will need to take the smallest child and make that node the new root so we'll swap our node with the smaller child and repeat the process swapping our node with the smallest child again and again until we reach a point where we've either hit the bottom of the heap or the node is less than or equal to both children at this point the heap will have the correct shape and we'll have made all of the necessary Corrections so that the heap invariant is preserved we now have a heap that is slightly smaller with the new smallest element at the root with this ability to add elements and remove elements from a binary heap we have all the pieces we need to implement our priority queue as we get new tasks we can add them to the heap we can quickly see the most important tasks and then we can remove it once it's done [Music]

Channel: Spanning Tree

Views: 36,742

Keywords: computer science, software, algorithm, dijkstra, binary heap, heap, min heap, max heap, insertion, deletion, prim, kruskal, mst, minimum spanning tree, a star, a*, search algorithm, graph search, data structures

Id: AE5I0xACpZs

Length: 8min 44sec (524 seconds)

Published: Thu Jul 16 2020