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

📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions

Question: Analyze Heap Sort's comparisons exactly in the best, average, and worst case of input data. Give an asymptotic bound for each case.

++++++++++++++++++++++++++++++++++++++++++++++++++

[BackToBackSWE]

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:

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.

[jkim]

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

[Stereotypical_Cat]

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

[alexandru-danielmarcu]

Who the heck is disliking such wonderfully crafted videos?

[memeingthroughenglish]

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

[koh]

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

[zerophive]

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!

[prajyotp]

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

[Travis-kojo]

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

[Zellie]

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

[mak]

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

[xfeedcafe]

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

[johabju]

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

[faridhashemi]

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!

[IceyBoy]

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.

[vhxhao]

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

[richardbux]

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.

[idanguttsait]

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!

[Dsoccerfreak]

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

[lougvar]

Amazing quality of the lecture. Thanks!