Investigating Heap Sort - Why Is Heap Sort Θ(n * log(n))? An Even Longer Really Long Answer. 

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.

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

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

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

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

Who the heck is disliking such wonderfully crafted videos?

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✌🏻

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

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 =)

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!

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.

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

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

Amazing quality of the lecture. Thanks!

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!

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

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

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

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.

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.

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

Very educative and well presented. Thank you so much

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

Awesome video man, thank you a lot!

very good structured explanation, thank you

Thank you sir, very clear explanation!

Great video! Huge thanks!

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

Thanks a million Ben❤it was realy helpful

The best explanation on the Internet. thanks

the best youtube chanel at all times

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

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

You are an excellent teacher.

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

just came across this video and I loved it

He explains the best on youtube

shoutout from reddit u da goat

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 ?

Amazing stuff!

I am so lucky that I came across your channel

Thank you, that was really clear :-).

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

Great work...

Great explanation!

@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.

Brilliant!

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

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

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

thanks bro

You are articulate

Please make a video on segment trees. Thanks in advance

your the best.

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.

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

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

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

where is the code in description?

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". :(

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

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

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

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

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

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.

You the doubts in my mind!

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

Where's the code of implementation?

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?

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

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

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!

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

Heap sort code seems missing from your GH.

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?

sir your remove Method Does Not Working Properly

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

INDEX! INDEX! INDEX!!!

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?

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

Okay, so....

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.