The main idea behind the heap sort algorithm is the tree 🌲 data structure. Watch this video for simple and short explanation of the tree data structure and the heap in particular. Video here : https://m.youtube.com/watch?v=40iljMQmqmY
The tree data structure is used for holding data that exhibits hierarchical properties for example, family tree where you show one or more entities under another etc. Now we can extend this idea to sorting. If a list of items is sorted say in an ascending or descending order, it makes sense to treat it as a tree i.e. a heap since one is bigger than the other (thus, under it) continuously in some fashion😃.
Given an array of items, we can present it in a heap data structure. A heap can be a Min heap or Max heap. A Max heap is one in which every non-leaf node is greater in value than all of its left and right children. What is meant by a leaf is a node with no any child.
Now of what benefit would it be when we simply present our data in form of a heap data structure 😒? The benefit we would enjoy in doing so as shall soon be uncovered, is same one experienced in merge sort - Mr. recursion 😂. A tree is nothing but collection of smaller trees. Yes! Each node with its two left and right child nodes is a tree. See the picture of a tree data structure if you doubt that. As such, we can simply use recursion to ripple through the whole heap and make it have the order we desire. If that's the case, what is then the point in using heap why not stick to the merge sorting? Recall that in merge sorting, we have to be making comparison at each merging stage for each of the element of the original array given , the maximum of which is equivalent to the number of elements in the original array given. Here, nothing like that at any stage and so, even before writing anything on the mechanism of the heap sort algorithm, we can foresee the time complexity to be far smaller than that of merge sort - in fact it is simply equivalent to the number of stages i.e. the recursive calls required to accomplish the whole process.
Are we actually building a heap physically? How do we make a heap data structure? There is no need of cracking our brains to come up with a new data structure that exhibits the heap; we can simply make a virtual heap. How😠? Simply put the list of items to sort in an array. Then superimpose the desired heap properties. For example, making sure that for each element position i in the array, the left child is at 2i and the right child at 2i + 1 and they should both be less in value than the element in that position i. Let's visualise that with the help of an illustration...
_-------------------------
DIAGRAM
_--_------------------------
Further, for Max heap specifically, the very first element of the array should be the largest in value.
Enough of mouth talks, lets make our hands dirty with the pseudocode for the heap sort.
Pseudocode of the Heap Sorting Algorithm.
The first step is building the heap for the data given. We can choose either the Min or Max heap whichever can do because in both as shall be seen soon, after building the heap, we have to finally replace/exchange the elements of the original array to achieve the sorted form. Simply building a Min heap doesn't guarantee sorting in ascending order because when a heap is created, it is possible that the left child is bigger than the right child which is acceptable in Min heaps construction but when it comes to reading the values say back into the array, we read from left to right and so, we get bigger element coming before a smaller one which shouldn't happen if our efforts is to sort in ascending order of magnitude.
Let's arbitrarily choose Max heap. So, let's write the line of pseudocode that can perform Max heaping on our data in our effort to implement the Heap sorting.
HEAPSORT(A)
1. Build-Max-Heap(A)
Now, we have a Max heap - for now, forget about how the Build-Max-heap works just assume it does its job correctly. Next thing to do is swap the first element (first node in the Max heap) with the last element, discard the last element and apply Max-heapify again i.e. make it a Max heap again. Here is the $1000 question. Why are we doing that 🤑 ? In a Max heap, whatever the case, there is always the guarantee that the very first node i.e. the root of the tree, is the highest value, bigger than any other in the whole heap. We exchange it with the very last node which is smaller but not necessarily the smallest (it might be bigger than a its sibling which is at the left ) . After this swapping, the last element is then discarded from the heap thus reducing the size of the heap by 1. In actual sense, it still exist in the array but only that we don't include it in the virtual heap. Since it still exist actually, and it is at the last position in the array, then that is what we desire; the overall largest element should occupy the last position. The next stage is then to Max-heapify the resulting heap without the last element in order for the overall largest element in the reduced heap to surface and appear as the very first element. Then we repeat the whole process by exchanging the first and last elements in the heap, reduce the size of the heap by 1 again so as to exclude the second largest element similarly. And we continue repeating such set of actions until the size of the heap becomes 2 and not 1 because once it reaches 1, it means the element is the smallest thus leaving it where it is; nothing to exchange it with! Hence, meaning the array is fully sorted. Don't forget that all we are doing is inside the original array without creating anything new; we just replace and exchange one element with another...
For (i=A.length downto 2)
exchange A[1] with A[i]
heapSize=heapSize- 1
Max-Heapify(A, 1)
The "for" loop goes from A.length to 2 as explained earlier. Each time, the heapSize is reduced just before calling the Max-heapify function and we have earlier explained why we do such. As the name suggest, the Max-heapify function creates a Max heap but doesn't make the whole heap a Max heap. All it does is making sure that from a particular node down, we have a complete Max heap; the particular node being the parent. So, for it to work, you have to pass into it, the particular node it should work on. Here, everytime, we pass in the first node. This is to reduce the amount of work instead of going through each node making it a (sub) Max heap as in what the Build Max heap function does which we shall soon see. Remember that just before exchanging the first and last elements, we had a Max heap which as a Max heap, must have with guarantee, the first left child greater than the right child. As such, following the exchanging action, all other things remain where they are. Applying Max-heapify, would then make the left child surface as the largest element now occupying the first node. But note that applying Max-heapify doesn't end here because as can be seen soon, we need to apply Max-heapify continuously downward in that line (through a since we make swappings which can make what was once a (sub) max heap, no longer a max heap and hence the need for further max heapifying.
That's all about the heap sort algorithm. But we just mentioned the Max-heapify and the Build-max-heap functions without writing how they work actually. Following are the pseudocodes and discussion on how each works.
The Max-heapify function takes the array's particular node (element position in the array) to make a (sub) max heap; do remember that any heap can be considered to be composed of smaller sub heaps. So, we have;
Max-Heapify(A, i)
The next thing is to check the left and right children which this node is a parent to. It has been found that the left child of any node at position i is the node at position 2i and the right child is at position 2i + 1. With these, we proceed to checking which of the children is greater than this parent node. When found, we swap so that the parent is the largest in size among them thus, making that particular sub heap, a max heap. Let's write those steps;
l= 2i
r= 2i + 1
if l<=heapSize and A[l] >= A[i]
largest = l
else
largest = i
if r<=heapSize and A[r] >= A[largest]
largest = r
if largest != i
exchange A[i] with A[largest]
Note 1: we always check if either l or r is greater than or equal to the heapSize as written above because once either of them is computed to be greater than the heapSize, it means the current position we are is the last position in the heap; in short no any left or right child and thus no need of proceeding any further.
Note 2:. This " != " Means NOT EQUAL TO. It needs no explanation to write this "if largest != i" before execution of the exchange statement because if the largest remains at the position of the parent, i.e. if the parent is the largest, why should we apply max heapify? - it is already a max heap.
Note 3: Never get confused. l, r, largest, and i are all positions not the actual values at the positions in the array or heap. So, largest means position of largest in the sub-heap, l means position of the left child, r is position of right child and i is the position of the current parent. Thus, "exchange A[i] with A[largest] " means to exchange the element at position i which is simply the parent, with the element at position of largest which might be either of the two left and right children depending on the result of the previous "if" statements.
But remember that, we said we need to continually apply max heapify downward after exchanging parent with a child so as to solve for the likely destruction of former max heap property which was in place before the swapping. But then when will it stop? We have already mentioned that but simply look into the max heapify function... Let's add that;
Max-heapify(A, largest)
Finally, the Build-Max-Heap function is nothing more than applying the Max-Heap function on all the nodes in the whole heap to make it a complete Max Heap. But do we have to apply the Max-Heap function on all nodes? Actually no! All we have to do is apply the max heap starting from the non-leaf nodes(the nodes at the lowest levels having no children) as it doesn't make sense to apply max heap on them since they have no children. Therefore, we start applying max heap on the first non-leaf node from the bottom up to the first node remembering that we don't have to care about the leaves because every max heap function applied on a node propagates or ripple through or is continually applied downward until hitting a leaf. It is worth keeping at the back of our minds that in a max heap, the right node can be greater in value than the left node; all we care about is the parent-child relationship i.e. for every sub-max heap, the parent should be bigger in value than both the left and right children. Let's write all that;
Build-Max-Heap(A)
heapSize=A.length
For(i=A.length/2 to 1)
Max-Heapify(A, i)
* Note that the it has been found that the non-leaves for every heap start from the node at position 1 upto the node at position A.length/2. Thus, that is why we run the for loop applying the Max-Heapify in that range. Also note that we set the heapsize equal to the number of elements in the array i.e. the A.length so that we utilise it in the Max-Heapify function to know when to stop the recursion(continuous call to the Max-Heapify function) which we said earlier that we stop once the left or right child is computed to be at a position greater than the heapsize i.e. out of bounds - more than the number of elements in the array which implies that we are done. All these was explained earlier- just to have everything handy with us so that we move along with all things.
Below, is the complete pseudocodes of the Heap Sort algorithm without any comment.
HEAPSORT(A)
Build-Max-Heap(A)
For (i=A.length downto 2)
exchange A[1] with A[i]
heapSize=heapSize - 1
Max-Heapify(A, 1)
Build-Max-Heap(A)
heapSize=A.length
For(i=A.length/2 to 1)
Max-Heapify(A, i)
Max-Heapify(A, i)
l= 2i
r= 2i + 1
if l<=heapSize and A[l] >= A[i]
largest = l
else
largest = i
if r<=heapSize and A[r] >= A[largest]
largest = r
if largest != i
exchange A[i] with A[largest]
Max-heapify(A, largest)
The tree data structure is used for holding data that exhibits hierarchical properties for example, family tree where you show one or more entities under another etc. Now we can extend this idea to sorting. If a list of items is sorted say in an ascending or descending order, it makes sense to treat it as a tree i.e. a heap since one is bigger than the other (thus, under it) continuously in some fashion😃.
Given an array of items, we can present it in a heap data structure. A heap can be a Min heap or Max heap. A Max heap is one in which every non-leaf node is greater in value than all of its left and right children. What is meant by a leaf is a node with no any child.
Now of what benefit would it be when we simply present our data in form of a heap data structure 😒? The benefit we would enjoy in doing so as shall soon be uncovered, is same one experienced in merge sort - Mr. recursion 😂. A tree is nothing but collection of smaller trees. Yes! Each node with its two left and right child nodes is a tree. See the picture of a tree data structure if you doubt that. As such, we can simply use recursion to ripple through the whole heap and make it have the order we desire. If that's the case, what is then the point in using heap why not stick to the merge sorting? Recall that in merge sorting, we have to be making comparison at each merging stage for each of the element of the original array given , the maximum of which is equivalent to the number of elements in the original array given. Here, nothing like that at any stage and so, even before writing anything on the mechanism of the heap sort algorithm, we can foresee the time complexity to be far smaller than that of merge sort - in fact it is simply equivalent to the number of stages i.e. the recursive calls required to accomplish the whole process.
Are we actually building a heap physically? How do we make a heap data structure? There is no need of cracking our brains to come up with a new data structure that exhibits the heap; we can simply make a virtual heap. How😠? Simply put the list of items to sort in an array. Then superimpose the desired heap properties. For example, making sure that for each element position i in the array, the left child is at 2i and the right child at 2i + 1 and they should both be less in value than the element in that position i. Let's visualise that with the help of an illustration...
_-------------------------
DIAGRAM
_--_------------------------
Further, for Max heap specifically, the very first element of the array should be the largest in value.
Enough of mouth talks, lets make our hands dirty with the pseudocode for the heap sort.
Pseudocode of the Heap Sorting Algorithm.
The first step is building the heap for the data given. We can choose either the Min or Max heap whichever can do because in both as shall be seen soon, after building the heap, we have to finally replace/exchange the elements of the original array to achieve the sorted form. Simply building a Min heap doesn't guarantee sorting in ascending order because when a heap is created, it is possible that the left child is bigger than the right child which is acceptable in Min heaps construction but when it comes to reading the values say back into the array, we read from left to right and so, we get bigger element coming before a smaller one which shouldn't happen if our efforts is to sort in ascending order of magnitude.
Let's arbitrarily choose Max heap. So, let's write the line of pseudocode that can perform Max heaping on our data in our effort to implement the Heap sorting.
HEAPSORT(A)
1. Build-Max-Heap(A)
Now, we have a Max heap - for now, forget about how the Build-Max-heap works just assume it does its job correctly. Next thing to do is swap the first element (first node in the Max heap) with the last element, discard the last element and apply Max-heapify again i.e. make it a Max heap again. Here is the $1000 question. Why are we doing that 🤑 ? In a Max heap, whatever the case, there is always the guarantee that the very first node i.e. the root of the tree, is the highest value, bigger than any other in the whole heap. We exchange it with the very last node which is smaller but not necessarily the smallest (it might be bigger than a its sibling which is at the left ) . After this swapping, the last element is then discarded from the heap thus reducing the size of the heap by 1. In actual sense, it still exist in the array but only that we don't include it in the virtual heap. Since it still exist actually, and it is at the last position in the array, then that is what we desire; the overall largest element should occupy the last position. The next stage is then to Max-heapify the resulting heap without the last element in order for the overall largest element in the reduced heap to surface and appear as the very first element. Then we repeat the whole process by exchanging the first and last elements in the heap, reduce the size of the heap by 1 again so as to exclude the second largest element similarly. And we continue repeating such set of actions until the size of the heap becomes 2 and not 1 because once it reaches 1, it means the element is the smallest thus leaving it where it is; nothing to exchange it with! Hence, meaning the array is fully sorted. Don't forget that all we are doing is inside the original array without creating anything new; we just replace and exchange one element with another...
For (i=A.length downto 2)
exchange A[1] with A[i]
heapSize=heapSize- 1
Max-Heapify(A, 1)
The "for" loop goes from A.length to 2 as explained earlier. Each time, the heapSize is reduced just before calling the Max-heapify function and we have earlier explained why we do such. As the name suggest, the Max-heapify function creates a Max heap but doesn't make the whole heap a Max heap. All it does is making sure that from a particular node down, we have a complete Max heap; the particular node being the parent. So, for it to work, you have to pass into it, the particular node it should work on. Here, everytime, we pass in the first node. This is to reduce the amount of work instead of going through each node making it a (sub) Max heap as in what the Build Max heap function does which we shall soon see. Remember that just before exchanging the first and last elements, we had a Max heap which as a Max heap, must have with guarantee, the first left child greater than the right child. As such, following the exchanging action, all other things remain where they are. Applying Max-heapify, would then make the left child surface as the largest element now occupying the first node. But note that applying Max-heapify doesn't end here because as can be seen soon, we need to apply Max-heapify continuously downward in that line (through a since we make swappings which can make what was once a (sub) max heap, no longer a max heap and hence the need for further max heapifying.
That's all about the heap sort algorithm. But we just mentioned the Max-heapify and the Build-max-heap functions without writing how they work actually. Following are the pseudocodes and discussion on how each works.
The Max-heapify function takes the array's particular node (element position in the array) to make a (sub) max heap; do remember that any heap can be considered to be composed of smaller sub heaps. So, we have;
Max-Heapify(A, i)
The next thing is to check the left and right children which this node is a parent to. It has been found that the left child of any node at position i is the node at position 2i and the right child is at position 2i + 1. With these, we proceed to checking which of the children is greater than this parent node. When found, we swap so that the parent is the largest in size among them thus, making that particular sub heap, a max heap. Let's write those steps;
l= 2i
r= 2i + 1
if l<=heapSize and A[l] >= A[i]
largest = l
else
largest = i
if r<=heapSize and A[r] >= A[largest]
largest = r
if largest != i
exchange A[i] with A[largest]
Note 1: we always check if either l or r is greater than or equal to the heapSize as written above because once either of them is computed to be greater than the heapSize, it means the current position we are is the last position in the heap; in short no any left or right child and thus no need of proceeding any further.
Note 2:. This " != " Means NOT EQUAL TO. It needs no explanation to write this "if largest != i" before execution of the exchange statement because if the largest remains at the position of the parent, i.e. if the parent is the largest, why should we apply max heapify? - it is already a max heap.
Note 3: Never get confused. l, r, largest, and i are all positions not the actual values at the positions in the array or heap. So, largest means position of largest in the sub-heap, l means position of the left child, r is position of right child and i is the position of the current parent. Thus, "exchange A[i] with A[largest] " means to exchange the element at position i which is simply the parent, with the element at position of largest which might be either of the two left and right children depending on the result of the previous "if" statements.
But remember that, we said we need to continually apply max heapify downward after exchanging parent with a child so as to solve for the likely destruction of former max heap property which was in place before the swapping. But then when will it stop? We have already mentioned that but simply look into the max heapify function... Let's add that;
Max-heapify(A, largest)
Finally, the Build-Max-Heap function is nothing more than applying the Max-Heap function on all the nodes in the whole heap to make it a complete Max Heap. But do we have to apply the Max-Heap function on all nodes? Actually no! All we have to do is apply the max heap starting from the non-leaf nodes(the nodes at the lowest levels having no children) as it doesn't make sense to apply max heap on them since they have no children. Therefore, we start applying max heap on the first non-leaf node from the bottom up to the first node remembering that we don't have to care about the leaves because every max heap function applied on a node propagates or ripple through or is continually applied downward until hitting a leaf. It is worth keeping at the back of our minds that in a max heap, the right node can be greater in value than the left node; all we care about is the parent-child relationship i.e. for every sub-max heap, the parent should be bigger in value than both the left and right children. Let's write all that;
Build-Max-Heap(A)
heapSize=A.length
For(i=A.length/2 to 1)
Max-Heapify(A, i)
* Note that the it has been found that the non-leaves for every heap start from the node at position 1 upto the node at position A.length/2. Thus, that is why we run the for loop applying the Max-Heapify in that range. Also note that we set the heapsize equal to the number of elements in the array i.e. the A.length so that we utilise it in the Max-Heapify function to know when to stop the recursion(continuous call to the Max-Heapify function) which we said earlier that we stop once the left or right child is computed to be at a position greater than the heapsize i.e. out of bounds - more than the number of elements in the array which implies that we are done. All these was explained earlier- just to have everything handy with us so that we move along with all things.
Below, is the complete pseudocodes of the Heap Sort algorithm without any comment.
HEAPSORT(A)
Build-Max-Heap(A)
For (i=A.length downto 2)
exchange A[1] with A[i]
heapSize=heapSize - 1
Max-Heapify(A, 1)
Build-Max-Heap(A)
heapSize=A.length
For(i=A.length/2 to 1)
Max-Heapify(A, i)
Max-Heapify(A, i)
l= 2i
r= 2i + 1
if l<=heapSize and A[l] >= A[i]
largest = l
else
largest = i
if r<=heapSize and A[r] >= A[largest]
largest = r
if largest != i
exchange A[i] with A[largest]
Max-heapify(A, largest)
No comments:
Post a Comment