Table of Contents: (This is long but very very thorough. Here is a table of contents. As always.) Helpful Resources & Ranting 0:00 - 1:39 Heap Sort Overview 1:39 - 3:32 Establishing Our Mapping System 3:32 - 9:03 Walking Though The "Build Heap" Phase 9:03 - 14:29 "Build Heap" Phase Finished 14:29 - 15:59 "Extraction" Phase Overview 15:59 - 16:58 Walking Though The "Extraction" Phase 16:58 - 24:12 Analyzing "Build Heap's" Runtime 24:12 - 26:21 There Is A Problem... 26:21 - 28:16 Diving Into Analyzing "Build Heap" In Detail 28:16 - 35:03 Analyzing The "Extraction" Phase's Runtime 35:03 - 38:53 This Is Why Heap Sort Is Θ(n * log(n)) 38:53 - 39:23 Camera Dies 39:23 Pre-Recorded Wrap-Up 39:23 - 39:58 My bad...camera died. I think I got the main points across though. Mistakes: 0:45 -> Nah...this is Ben from the future. Algorithm analysis and doing the math is tricky...but understanding these basic algorithms is straight-forward. 1:44 -> Misspoke. I didn't mean just Big O. As you visually see those are the bounds on the respective cases. 6:48 -> 7 is not greater than the elements below it. Not sure what I was thinking...probably was not thinking. 27:06 -> There technically is no big and little Theta. It is just Theta because there is no little theta. My bad, I was in the zone. Resources: - Excellent Explanation For Why The "Build Heap" Phase Can Be Tightly Bounded To The Order of Linear Time: www.cs.umd.edu/~meesh/351/mount/lectures/lect14-heapsort-analysis-part.pdf - Stirlings Formula: en.wikipedia.org/wiki/Stirling%27s_approximation My Comments: - The code in the description is for insertion and deletion from a binary heap. All you need to care about is the bubble down function as well as the index mappings we discussed. - All heapsort does is build a max heap (as described in the video) and then extract from it (as described in the video). The code shows you how to do both of those.

This is literally saving my college grade, thank you kind sir

I got my first full-time offer yesterday! Huge thanks to your channel!

Thank you! This one finally made heaps and heap sort click for me. You have great tone and clarity. Enjoying the rest of your videos!

homie, you're killing it. gonna post up your channel as a resource for my peeps at school

Love the passion for the topic. I would never click on a video longer than 10 minutes, except for your explanations.

You are so good at teaching. You’ve made me enjoy learning algorithms again. Thank you.

Finding your videos in my feed is very luckiest thing done to me in my CP career. Thanks✌🏻

This is by far the best channel about algorithms and data structures, I'm not even an english speaker but this is so clean and understandable, thank you so much =)

Everything bubbles into place now - I finally understood it, just in time for exams! Thanks so much for a great, well thought out video

Who the heck is disliking such wonderfully crafted videos?

Amazing quality of the lecture. Thanks!

Hey man, thank you so much for this amazing video! I haven't seen heap sort before and learned it from your video, and the explanations about the upper and tight bounds were great! Honestly after so much time of being afraid of math and not quite seeing what I can earn from it, this video alone has made it a little clearer where math comes in, And gives me some motivation to actually go for a degree sometimes in the future, so thank you!

Awesome video. Appreciate your hard work this explanation has helped me with my studies.

It was really a great explaination. Thank you for it. One thing that i want to specify which is something that not everyone has the courage to do, admittiing their own mistakes, what really matters is to act with good intentions. Keep it up. Keep posting.

the best youtube chanel at all times

Another brilliant explanation. Thank you for this! All the best for realizing your vision! I really do believe that it’ll happen :)

Thank you for breaking down the steps. I finally can understand the algorithm.

Very educative and well presented. Thank you so much

He explains the best on youtube

Huge thanks for the help, fam. We all owe you one

The best explanation on the Internet. thanks

shoutout from reddit u da goat

very good structured explanation, thank you

You are an excellent teacher.

Thank you , very clear explanation! Your videos are very helpful. I am sooo happy to learn data structure with all your videos ~~~

You are amazing man. They way you teach is completely different from how my teachers teach here in India and this suits me. Thanks man.

Awesome video man, thank you a lot!

Great video! Huge thanks!

Thank you sir, very clear explanation!

Hey man, thank you so much for creating this awesome content. I'm currently studying a masters in cs and your way of explaining concepts is brilliant, it's helped me so much. Keep up the great work!

I love to watch your videos related to algorithm . Congratulations keep growing well ❤️

Why don't people like your videos. They are so good. You have so much patience. Become a teacher or something. God bless u man

Love the videos. Just wanted to point out small mistake- at 6:53, both 6 and 7 are out of place, given we want to make a max heap

You're amazing. I just came here to watch the part you said one can skip it

Amazing stuff!

just came across this video and I loved it

Thanks a million Ben❤it was realy helpful

I doubt you will read this, but your videos have been fantastic. I feel like I'm able to get ahead of my peers at uni cause you explain these concepts extremely well. Thanks for the content.

Years after, and this is the best channel to study algorithms

Great explanation!

I am so lucky that I came across your channel

Great work...

Please make a video series on hash table data structures interview questions.

Thank you, that was really clear :-).

Brilliant!

your the best.

hey, thanks for the amazing videos! quick question, what kind of math do we have to do to understand whatever mathematical formulas we see in your video ？ how good do you have to be at math ?

You are articulate

@17:34 I think it would be better to explain why we need to move root node to the end. Because if we remove the first element on the list, we need to shift rest of the array by -1. By swap first and the last, it will save computation time.

Believe or not bro.. but I am very eagerly waiting for your next videos. The minute you upload it, I will watch even if I am anywhere. I have interviews coming within a month. Wish me luck. Love from India

1:51 - heapsort can do O(n) in best-case if keys are equal as wikipedia says

thanks bro

log(n!) is smaller than n×log(n) Cause log(2)+log(3)+log(4)+...+log(n)

Hey man! Thanks for your videos! Where exactly is the code in the description?

Please make a video on segment trees. Thanks in advance

I cannot find the code in the description. Where is the code?

I dont understand anything of what youre talking about because programming its not my field at all and yes, logarithms make me uncomfortable, but still I can tell how well made your video is made, its always nice to find great content creators no matter what content they make.

where is the code in description?

Can we say it is like 1.build heap 2.extract 3.immediately build heap 4,extract and so on I think this is what you mean please confirm sir

I'm a student of Computer Science in Brazil and I got wrong in a test question about "heap sort complexity". The teacher explained that I have the wrong concept of heap sort (the concept apresented in this video): The tree starts empty and the elements are added to the tree to construct the "heap". According to him, it's wrong to say that the "tree is already built and I have to turn it into a heap", but, yes, the correct thing would be to build the tree and, at each insertion, to modify it so that in the end it becomes "heap". :(

what about exact lower bounding? I came here for that...

also you should talk abiut building heap when all elements are not available at one, you get elements one by one, like median of infinte stream type questions

Could you do an in depth on red-black trees lol

to end u sud wnd with so heap sort has 2 stages one is making max heap which is o(n) and then doing the heap sort which is n*logn

You the doubts in my mind!

Quicksort fans complains on cache misses but space complexity constant there is no explicit extra space like in merge sort nor implicit hidden in recursion Time complexity is O(nlogn) even for worst case That's why this was my favourite sorting algorithm when i used to go to school

Where's the code of implementation?

art 25:58 how come O (n/2 * something) is equal to O(1/2n * something)??

what about 15, its index 4, 4-1/2= 3/2=1.5, i am assuming they using int not float and getting correct answers.

Thank You Very Much for the great and informative video. I have a question though (pardon my ignorance). When a max heap is represented as array, the max number is always at index 0. But after a full heap sort we always have the max at the last index of the array i.e. the visualization of the tree would be exactly opposite. What is the reason for this? This actually threw me off and ended up wasting my time writing code without understanding the full heap sort and Thanks to you, you made it very clear. Thank You again

I believe that a heap is an almost complete tree and not always a complete one. i.e. the second to last row don't all need to have children

@6:56 how is 7 larger than 17 and 12???

is.. is it just me or is he secretly drawing bay-max in his explanations?

You lost me at 16:06, you have a max heap. What do you mean you're doing placements?

Please do confirm that: Is heapSort O(n log n) ? or O(n lg n) Because, lg n = log(base 2) n, which is the binary logarithm. 1:51 Thanks!

17 and 12 are not bigger than 7, I'd suggest you fix it with an annotation for clarity. @6:55

6:52 on what planet is 7 larger than 17 and 12?

Heap sort code seems missing from your GH.

sir your remove Method Does Not Working Properly

wait, 7 is greater then its children ??? @8:03

Are you really a graduate student ? Or post graduate??

Benyam: Is 7 larger than any element below it? Me: 17 and 12 are greater than 7, so that would be no. Benyam: Yes, it is. Me: Wut?

was hoping this would be a good explanation of heap sort, but the constant quick random popups is a really big distraction. do you really need to flash heap sort all over the screen real quick?

INDEX! INDEX! INDEX!!!

Okay, so....

I don't know how to Buid a heap as you have it spelled at 2:10.

See Trump? Us black people can code!

Who cares about all this bound crap? I think it is more interesting to know the actual time it takes to sort something in seconds. Why would I care if something is O(n^2) vs O(n log n) if the O(n^2) algorithm just happens to run in less time than the O(n log n) which is possible? I would rather hear something like heapsort takes 5 seconds to sort 1 million random 16 bit integers in place on a 3 Ghz single core Intel CPU computer whereas Mergesort takes n seconds and Quicksort takes m seconds. To be very fair, store and re-use the same 1 million random numbers used in the first sort so they are all sorting the same exact input.

dude, the constant popups all over the place is driving me crazy. rethink your format.