Sort Lists with Heap Sort in Python

[Music] hey everyone in this video we're going to take a look at how to implement the heap sort algorithm it's a very intuitive sorting algorithm so that we can sort any list either in ascending or descending order depending on whether we choose to use a min heap or a max heap so a heap is a binary tree such that every parent node is greater than both of its children node that's what we would call a max heap if we wanted to use a min heap that's going to be where every parent node is less than or equal to its children so in this case we're going to implement this using a max heap let's start off by drawing this array as an incomplete heap so we'll draw it as a binary tree but we won't actually heapify it until the next step so we have five in the beginning and then 16 and then we have eight and then under 16 we have 14 and 20 and under 8 we have 1 and 26 so to heapify this we have to consider the last parent node so that's going to be this 8 right here this is going to be our last parent node because all the rest of the nodes are all leaf nodes they don't have any children for each other so we consider 8 so 8 is greater than 1 but 8 is not greater than 26 so we want to move 26 up so we'll move 26 up here and we'll move 8 down here now let's move to 16. well 20 is greater than 16 so we'll swap those two positions now we have 20 and 16. and now we move up to the root node which is 5. so both 20 and 26 are greater than 5. so we're going to choose the larger of the two so we'll move 26 to where 5 is and we'll move 5 to where 26 is so 26 is now the root and five is now where 26 was and then we have to continue sifting down five until we have a heap so five is going to switch with eight so we'll put an eight here and we'll put a five here and that's all we have to do for this now we have a heap so if we were to write this in order we would have 26 20 8 14 16 1 and 5. now this is not in sorted order but we do notice one thing and the thing that we notice is that the very first element in a max heap is always going to be the largest out of any of the elements in the heap so we're going to make use of that so what we're going to do is we're going to iterate n times where n is the number of elements and for each iteration we're going to take the topmost element so that's going to be the first element and we know that's going to be the largest so we're going to move that element to the end and we're going to move whatever element was at the end to where this largest element was to index zero and then we're going to sift down five until we have a heap once more and and so there's something special about the sifting down in this particular step so we'll cover that when we write this out so we switch these two and we get 5 20 8 14 16 1 and 26 so now when we go to sift down 5 to make it a heap once again we're actually only going to consider this portion as our heat because we don't want to touch anything that's after this index since after this index it's all going to be sorted so here if we want to see what it looks like all we've done is moved the 26 here and i'll just write this in red to indicate that we're no longer going to look at that and then we move a five here and now we just have to heapify this heap such that we're not actually going to consider any elements in red since they're already sorted in our list they're already partially sorted so here we're going to move 5 down in this direction because 20 is greater than 8 and both are greater than 5. so we'll move 5 here and we'll change this with 20. and then we will move 5 once again to where 16 is so we'll swap these two and now five is all the way at the bottom so now our next element at the top is 20. so that's the one we're going to pull out next and we're going to swap that with the last element so keep in mind now the last element we're actually considering to be 1 and not 26. so our list at this point before we sift down any further is going to be 20 16 8 14 5 1 and 26. so now we swap 20 and 1 and our resulting list is going to be 1 16 8 14 5 20 and 26 and so we do the same steps here so what we did essentially was we just swapped these two here so this became a 20 and this became a one and now we just sift down one so 16 is the greatest child so we'll move one down here we'll keep 16 here and then we will swap 1 and 14. so this will become just 1 and this will become 14. and so now our list looks like this so we have 16 14 8 1 5 20 and 26 and keep in mind that 20 and 26 are already in sorted order so we don't have to consider these when we're heapifying our list later on so let's move this up here so we have more space to write so now our next element that we're going to move is going to be the 16 and it is going to be swapped with the five so we can swap these two and now this one will be five and this one will be sixteen and now we can heapify this heap considering only five fourteen eight and one so fourteen is the greatest child for five so we will swap 14 and five so this becomes 14 and this becomes five and then we have to swap five and one keep in mind we don't consider 16 because it has already been sorted so this moves up here and now our next step is we have to move 14 down so we can swap 14 with 5 because 5 is our last element here so we'll move 14 down here and 5 here and actually we can replace this with red because now 14 is part of our sorted list and now we have to sift down five so five can replace eight and eight can replace five so we'll swap those two and now our next element is eight and we're going to switch that with the last element which is five in this case so we'll swap these once again and now we can consider sifting down five but the only child for five is one and five is greater than one so we don't have to sift it down so we can keep five where it is and now one of our last steps is going to be swapping five with one so we'll swap those two and we should get that one has nothing to swap with so it stays how it is and finally we swap one with itself to get one and thus we have a sorted list from 1 5 8 14 16 20 all the way to 26. so this is an unstable algorithm but it's still helpful if you're going to do sorting in any small way so let's go ahead and implement this algorithm so there are a few functions that we're going to define for our algorithm so we need a main heap sort function the dev keep sort and it's going to take a list as input and we'll just sort the list in place we won't generate a new list and return that so we'll need that function and then for that function to work we need two subroutines we need a swap function let's say def swap list i j so we're going to swap at indices i and j for our list and so we'll just put a pass there and then the second subroutine that we need is a sift down function so def sift down list i upper so this will help us to initially heapify our list and then every time we want to pull the largest element from our heapified list we can sift down the element that we swap with the largest element so that we maintain a max heap so we'll just put a pass here for now so let's just start off with the easiest function so the swap function is quite simple all we have to do is say list bracket i list bracket j is equal to list bracket j less bracket i and this is quite simple you don't need a function for this but it just makes it more concise here we don't have to write out this verbose piece of code now the next part is the sift down function so whenever we want to sift down a particular element this is going to be when we're both heapifying our list and when we're sorting our list we want to be able to move the topmost element down so that we have the new topmost element being the largest so we'll put a loop here while true and you may see in other instances that some people like to use recursion here but i'm going to stick with the loop because if we use recursion and we decide to perform the sift down function on a very large list we could end up with a recursion error because we go up to a certain limit whereas with loops we don't have any such error except for a logical error when we do an infinite loop so while true we want to sift down our parent if needed to one of the children if there are any children so first we have to get the indices of the children so with the heap we can say l comma r is equal to i times two plus one and i times two plus two so here i represents the current parent index at the very beginning of this function call it's going to represent the root node of our tree and we're doing i times 2 plus 1 and i times 2 plus 2 as our left and right indices because this is how we can refer to the children of any parent node in a heap so these are the indices of left and right children and then we have a few conditions to check so first we have to see if there are two children and if there are two children we're going to do something but if there's only one child then we only have to do something with that one child and then we also have to consider if there's the other child or maybe if there are no children so let's first consider if there are two children for this parent node so if max l comma r is less than upper that means that these two indices are valid so up upper here indicates the upper bound of our list that we are intending to consider as a heap so maybe upper might be somewhere between zero and the length of the list and wherever upper is we're only considering our heap to be from zero to that upper limit so it doesn't necessarily include the entire list and that's because when we're actually sorting our list we want to keep the items after upper to be the same because those have already been sorted so here if max of l comma r is less than upper that means we have two children now we can check if the parent is greater than both children so if list bracket i is greater than or equal to max ltl and ltr if that's the case then there's nothing more we have to do here we can end the sift down subroutine so we can just say break now that's not the case then we want to swap the parent with the larger child so there's two cases here the left child is greater than the right one or the right one is greater than the left one so alif list bracket l is greater than list bracket r that means we want to swap the parent node with the left child the swap list i l now otherwise we want to swap with the right child so list i r so here we have swap list at indices i and l and here we have swap at list indices i and r but before we actually end these two we need to add two more lines of code in this condition so we have to say i is equal to l because we have to move down our pointer for our parent node every time we sift down we have to update the parent to reflect the new parent that we're going to evaluate in the next step so here i is equal to l if that's the case because we swapped with l and here on line 14 we're going to say i is equal to r because we swapped with r so we're going to change that pointer to index r now outside this condition on line 7 we want to check if only one child exists so let's consider the left child so l if l is less than upper that means we have a left child now we want to check if this child is greater than the parent so if list bracket l is greater than list bracket i if that's the case then we want to swap at those two indices so swap list i l and then here of course we need to update the parent node to be the new parent node which is going to be at index l because that's where we swapped so i is equal to l now in the case that this condition fails that means that there's no longer a need to sift down so we can break out of this loop so else break now in addition to checking if the left child exists if that doesn't work we have to check if the right child exists so l if r is less than upper and we're basically going to do the same thing as we did from line 16 to 19 except this time with r instead of l so if list bracket r is greater than this bracket i we want to swap at those two indices and then we want to update the parent node to be at index r so i is equal to r otherwise there's no need to sit down any further so we will just break now the last condition we have to check is that if there are no children if there are no children that there's no sifting down that we have to do because there's no children to actually swap with so else brick and so that's all we have to do for our sift down function so the final part of our algorithm is to actually implement the sorting component so that's on line 27 and onwards we're going to define heap sort so there's two steps here the first step is to heapify into a max heap and the second step is to actually sort this so in the first step we'll say for j in range length of list minus two florida by two and you can just verify that this number is correct if you go earlier in the video because you'll notice that this index refers to the very last parent because any leaf node we don't really have to check since those leaf nodes aren't going to have any children to swap with and then we will end at negative one and we will decrement by one and so in here we can just say sift down at list at index j and our upper bound will be length of list so here this loop essentially heapifies our entire list each sift down step is going to sift down each number that we encounter but here we're just iterating through every item in our list so that essentially heapifies it so the final part is to implement the sorting component so we can say for end in range length of list -1 and we'll stop at zero and we'll say minus one and the reason we're stopping at zero is because by the time we get to index zero everything else is already sorted so the number that we're currently at is also part of a sorted list in its entirety so here the two steps we do is we say swap at list index zero and end and once we do that swap we sift down the new first element so that'll be sift down list at index zero and our upper bound is going to be end so that just basically means we don't want to consider any item at index end all the way to the end of the list to be part of our heap that we are essentially heapifying and this is all we have to do for our algorithm so we can test this out so let's go ahead and take our list that we tested out before in the video so list is equal to 5 16 8 14 20 1 and 26 and we can say heap sort on list and let's just print list to see what that outcome is so i can run this in the console and i should see that i get a sorted list from 1 to 26 and this is going to work for any list so maybe i might change up this list so that it is in reverse order and i want to sort it in ascending order so maybe i say this is equal to i for i and range 101 negative 1. so this will be all the numbers from 100 to 2. and let's heapsort this and we can run this and we should see that we get all the numbers from 2 to 100 in increasing order so that's it for this video and i hope this was helpful

Channel: CodeSavant

Views: 3,451

Keywords:

Id: laYrbOAmuvQ

Length: 16min 44sec (1004 seconds)

Published: Tue Apr 06 2021