Step by step instructions showing how to run heap sort. Code: github.com/msa... (different than video, I added this retroactively) Source: ind.ntou.edu.tw... LinkedIn: / michael-sambol
Wriwitng pseudo code is easy once you understood the algorithm. Reading someone's pseudo code on the other hand can be quite annoying, because they may use different naming conventions, different syntax and even different "language" than you.
I guess Im randomly asking but does someone know of a method to get back into an Instagram account..? I somehow lost my password. I appreciate any tips you can give me!
I am genuinely impressed at how shit my professor is he takes 5 slides to explain this and never asks any of the many questions i had. This video did more for me than 2 lectures.
First i felt why u didnt explain how to build max heap but then it becomes clear as thats not the point of video and can be learnt seperately. You are making these look so simple. Thumbs up to you.
The best part is the very last portion where everything is summed up and pseudocode is given. Thanks! Exploring more videos to prepare for an interview!!
@@raphaelandrade555 Consider this: someone's native language is English and has lived in Japan for 2 years, and this person makes a video in Japanese, which incurs some native Japanese speaker saying "he's not saying proper/bad Japanese". It's like laughing at a 1-month-old not being able to walk.
it manages O(n) by using a bottom-up approach. Each sub-tree in a heap must also maintain the heap property. When you run build-max-heap the runtime depends on the height of the tree. Since you can safely build a heap bottom-up, you would get something like this: O(n + (1/2)n + (1/4)n + (1/8)n + (1/16)n + ...), which simplifies to O(2n), or just O(n). That's not exactly what happens, but it's along those lines. You should google "linear time build heap" for more info.
i know this is a little late but thank you so much for this video!! the way you explained it, i understood this much better than when my prof talked about it in class. bonus points for the pseudocode at the end :D
I think the array you used in this example might be misleading, as when you do the max-heap you obtain a descendent sorted array and from there you can just flip it to get the sorted array.
@@AahanaHegde-py7ng max-heap just ensures that the parent node is greater than its children which doesn't guarantee that the tree written in the array form will be sorted in descending order. For example, when the original array has max-heap applied to it in the video it returns the array 9 8 5 3 2 1 (which is sorted descending). However, if you look at the representation of the tree in the video and imagine flipping the left sub tree with the right you would get the array 9 5 8 1 3 2. This still satisfies the condition that the parent node is greater than the child, but the array is no longer sorted.
1:38 and we are done, just call reverse on the array.... wait why are you messing it up again? I think the example data made this more confusing as it ended up sorted after the first build-max-heap call.
I'm confused. Why do you need two functions for this? In both cases the input was a tree and the output was a max heap. Maybe it's because we know that after the first one it's only the root node that is out of place, and we use another function that doesn't do unnecessary calculations related to other nodes. Then it'd be better if the name was more descriptive. Considering how it doesn't operate on the whole tree, it can be named something like heapify_branch instead
Could you take a look at the full playlist, I think it will help: ru-vid.com/group/PL9xmBV_5YoZNsyqgPW-DNwUeT8F8uhWc6. Code: github.com/msambol/dsa/blob/master/sort/heap_sort.py
1:35 At first function call of "Build Max Heap" we have sorted array in descending order, we fix this simply by swapping. Why are we performing these many operations ? Anyone please !
hash sort by distribution function (for example linear) direct bin division placement, subsort each bin, O(n), divide and conquer, extended quick sort by multiple pivots at once, the bins
Lokesh Joshi it was a coincidence that his max heap was already sorted in descending order. That will not always be the case. Should be a different example to avoid confusion like this
Brother please make a video on threaded binary tree insertion, your videos are great and in less time, great for revisions and understanding complex concepts easily and quickly ❤
What's the point of heap-sorting when we already have a sorted max-heap at 1:40? Yes, it's sorted backwards, but heapsorting takes more time than reversing a sorted array. I don't really get it. EDIT: I got it and I think the example used in the video wasn't that good, because a max-heap doesn't necessarily end up being a sorted array.
I'm very confused about something. When you call build-map-heap, you are sorting the entire array in descending order. At that point, the array is sorted. Why would you keep sorting after that point?
for example, left child can be less than right one, so now array is unsorted UPD: the left child of right child can be greater than the right child of left child. This try must be correct :)
Yes it's sorted but remember that it is *heap-ordered* and the resulting array is in the binary tree notation. The last portion of the algorithm is still necessary to have a sorted array by making use of the heap ordered array by continuously removing the largest element and reheapfying until you get your sorted array
@@azzam7239 I don't really understand, in all the examples I see, the heap is physically stored as an array, and max heapify sorts that array perfectly, so why don't we just use that array?
I wonder if on average, plucking the 2 largest elements from the maxheap (if available), will speed things up. It seems wasteful to not pluck 2 at a time since we know the 2nd one will be one of the roots children. I traced this example on paper and it seems to work well. However I would like to know on say a 1 million entry tree (19 levels deep), how much faster it would be in real time. I would want to randomly generate 1 million numbers, store them for input to both "flavors" of heapsort, then make a table of outcomes. For example, 4.7 seconds classic heapsort, 4.6 seconds modified heapsort. I would also want to try cases with 1 million unique numbers, cases with 1 million small numbers with lots of repeats (like in the range 1 to 1000), and 1 million numbers with large gaps (like use 1 million random 32 bit numbers). I think the results would be interesting. Maybe someone can try it and report back.
So, when you do max heap the first time, you get a sorted array but in a different direction. Can't you just make a new array that has the same values, but reversed and you are finished with the sorting?
@@kylestormeyes4976 Actually, It is not correct. It only happens in certain cases, and this one is one of them. I should've deleted the comment when I realised that.
Is it right to assume that a Heap is ordered? We know that the heap property guarantees the greater or smaller relation between parent and children, but the overall tree may not be exactly ordered.
Thank you for the reply. But in this case for BuildMaxHeap() we call Heapify() n/2 times and each time costs O(logn) time, so the total time complexity is O(nlogn). Is there anything not proper?
魏雍 incorrect because the heapify for nodes at height h-1 only trickle down once, the ones above it trickle down twice, and so on. So for each level, the amount of work goes down as you go deeper into levels. Not each one of the n/2 nodes will do logn work! in fact the only one that will do logn work is the root node :) I suggest you have a look at CLRS. It shows the correct way of computing this tighter bound.
what a great video, thank you! I think there is a mistake in the pseudo code in BuildMaxHeap. if you assign i to start from n then the index of the last element is i-1 and not i. it's better to assign it to start from n-1 and then you don't need to subtract n after the swap. also, you put 1 instead of n when calling the Heapify function.
Trying to understand build-max-heap and heapify here. Based on your explanation, build-max-heap arranges the tree so that the highest value goes to the top, forming max heap, then you swap it with the last element (bottom right) in the tree and remove it from the tree. Then you call heapify to gradually move the last element situated on top down for the child nodes (having higher value) to go up. How does the node choose which immediate child node to promote? And if what heapify does reiteratively is to eventually move the highest value node up to the top, why cant we call build-max-heap in the beginning?
