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

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

[@utsavprabhakar5072]

one suggestion. If you mention a video , please provide the link for the videos mentioned. Thanks in advance. Great content otherwise. cheers!

[@BackToBackSWE]

ye

[@khilarihemanshu7581]

@@BackToBackSWE you should also walk through the pseudo code in the end of such videos

[@BackToBackSWE]

@@khilarihemanshu7581 ok

[@foobars3816]

@@BackToBackSWE I came here to say the same thing as Utsav Prabhakar. You still haven't linked to the mentioned videos mentioned at 0:17, even though you liked his comment and responded with "ye"? I have annotations turned on and I still don't see anything and there is still only one of the three links in the description. I ended up finding them by guessing keywords you might have used and doing a search of your channel. If you want to get more views on your videos this will help a lot, because most people won't bother searching for the videos and instead just thumbs down when/if they get stuck.

[@jkim5118]

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

[@BackToBackSWE]

congrats...don't make me cry 😢

[@mnamaddy]

@@BackToBackSWE 😂😂

[@Stereotypical_Cat]

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

[@BackToBackSWE]

nice, internet friend

[@alexandru-danielmarcu7100]

Who the heck is disliking such wonderfully crafted videos?

[@memeingthroughenglish7221]

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

[@Travis-ko2jo]

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

[@BackToBackSWE]

thanks. hey.

[@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!

[@BackToBackSWE]

great

[@prajyotp4981]

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

[@Zellie1994]

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

[@0xfeedcafe]

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

[@mak5386]

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

[@BackToBackSWE]

sure

[@IceyBoy47]

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.

[@BackToBackSWE]

People use that preface but like I read everything. Nice, good for u, keep going young one

[@IceyBoy47]

@@BackToBackSWE Also quick question if you can respond, is there any other materials you could recommend for data structures and algorithms in general or other concepts that might be useful to understand regarding the topic?

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

[@BackToBackSWE]

ah yes, I think I address this in the teacher's notes?

[@faridhashemi8484]

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!

[@BackToBackSWE]

Happy Holidays 🎉 Thank you for your kind words, Farid! We'd love to offer you a 40% Off our exclusive lifetime membership just use the code CHEER40 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=CHEER40

[@koh8614]

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

[@richardbux8079]

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.

[@BackToBackSWE]

thanks.

[@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!

[@BackToBackSWE]

U can do whatever u wanna do.

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

[@roshannayak1463]

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.

[@mehmetdedeler2247]

the best youtube chanel at all times

[@lougvar]

Amazing quality of the lecture. Thanks!

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

[@BackToBackSWE]

thanks

[@cesareriverso5544]

He explains the best on youtube

[@bronzebond4869]

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

[@rothenbergt]

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

[@BackToBackSWE]

awesome, glad it helped

[@MajdBousaad]

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

[@shreyaskharbanda2777]

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

[@BackToBackSWE]

sure

[@christiantith2843]

shoutout from reddit u da goat

[@BackToBackSWE]

🐐🐐🐐🐐🐐🐐

[@jsceo]

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

[@BackToBackSWE]

We discuss worst case

[@chrislau5394]

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

[@BackToBackSWE]

great

[@pushpendrasingh1819]

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

[@BackToBackSWE]

hahaha wassup! yall' Indian people are cool

[@sakar276]

The best explanation on the Internet. thanks

[@samirp9002]

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

[@BackToBackSWE]

n/2 = (1/2)n, right? am I missing something

[@Firstusee256]

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

[@BackToBackSWE]

I will. This project will take at least a year. These topics will get covered eventually. Thanks.

[@kattuvasi_arun]

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

[@BackToBackSWE]

hey

[@kattuvasi_arun]

@@BackToBackSWE hi, how are you

[@cobysoffer4488]

I am so lucky that I came across your channel

[@samcheng1734]

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

[@BackToBackSWE]

nice! thanks

[@kinshowa17]

You are an excellent teacher.

[@BackToBackSWE]

thanks, hey

[@Talastals]

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.

[@BackToBackSWE]

Thank You, Glad you liked it. Do check out backtobackswe.com/platform/content and please recommend us to your family and friends :)

[@흠냐링-i4y]

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

[@BackToBackSWE]

ye

[@fredokoh5633]

Very educative and well presented. Thank you so much

[@GERSHON123]

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

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com now.

[@hariharansubramanian8784]

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

[@BackToBackSWE]

Im not sure

[@akif511]

very good structured explanation, thank you

[@robertgabriel1190]

Great video! Huge thanks!

[@BackToBackSWE]

sure

[@emmanueltejeda7484]

just came across this video and I loved it

[@BackToBackSWE]

hey

[@WowPlusWow]

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

[@BackToBackSWE]

1.) You could have simply said "At 6:52 I spotted a mistake where you said '7 is larger than 17/12'". 2.) Check the pinned note this has been addressed.

[@WowPlusWow]

@@BackToBackSWE Thanks for the reply and sorry about the rude and arrogant comment. Your videos have been helping me a lot with preparing for coding interviews and studying for my exams.

[@fatimakhan763]

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

[@BackToBackSWE]

check pinned comment

[@MinhLe-xk5rm]

Awesome video man, thank you a lot!

[@BackToBackSWE]

sure

[@guowanqi9004]

Thank you sir, very clear explanation!

[@BackToBackSWE]

sure

[@maedeelyasian7070]

Thanks a million Ben❤it was realy helpful

[@BackToBackSWE]

ye

[@JonnieZuramski]

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

[@BackToBackSWE]

please see pin.

[@liaskarllate]

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

[@BackToBackSWE]

nice, how's the weather in Brazil? Here in SF it is cloudy a lot

[@liaskarllate]

@@BackToBackSWE I just wanted to share what happened to me. This doesn't disqualify your content which, by the way, is very good. I congratulate you for the great work. But, my teacher has a closed mind on different form of implementing some algorithm. The way he expected me is that one presented in Tenenbaum's "Data Structures Using C" book, which is different from all the forms that I found on the internet. I apologize if my comment has offended you or your content in any way.

[@BackToBackSWE]

@@liaskarllate no it didn't haha

[@sayyidalisajjadrizavi7418]

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!

[@BackToBackSWE]

log(n) and lg(n) say the same thing. lg(n) is shorthand for log_2(n). And log(n) is under base 2 in this case.

[@holyshit922]

Base does not matter in asymptotic notation because according to change of base formula for logarithms it differs by constant factor

[@sayyidalisajjadrizavi7418]

@@holyshit922 I see what you mean is: log n = log_2_n / log_2_10 = log_2_n / 3.33 = (1/3.33)(log_2_n) Thanks!

[@theonlyarkitekt]

Amazing stuff!

[@holyshit922]

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

[@BackToBackSWE]

indeed

[@holyshit922]

@@BackToBackSWE In textbooks i have seen array implementation of heap so far For sorting data structures like linked lists BST would be helpful (procedures like inserting to BST , inorder traversal with inserting node after tail)

[@butteredtequilla9046]

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

[@BackToBackSWE]

You can check out the code repository on backtobackswe.com/

[@csek118madhavislavath9]

where is the code in description?

[@shaunzeng5996]

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 ?

[@BackToBackSWE]

Not very, just know summations and algebra.

[@tianmingguo8271]

Great explanation!

[@BackToBackSWE]

Thank you, glad you liked it 😀 Do check out backtobackswe.com/platform/content and please recommend us to your family and friends 😀

[@aleyummusic]

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

[@BackToBackSWE]

We extract from the top of the max heap 1 by 1. The max heap is just conceptual. The whole time we just have an array. The conceptual max heap reduces in size on each removal.

[@dawn-of-newday]

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.

[@dream11tatyabichoo92]

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

[@BackToBackSWE]

what

[@dream11tatyabichoo92]

@@BackToBackSWE what u didnt understand in this , for heap sort to work you first make max heap which is theata of n and then you do the sorting which is 0 of n logn

[@davitmelikidze9030]

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

[@rudolphbennett3988]

Thank you, that was really clear :-).

[@dream11tatyabichoo92]

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

[@BackToBackSWE]

not fully sure what you mean?

[@dream11tatyabichoo92]

@@BackToBackSWE here all items are available at once we are using heapify which bubbles elements down but elements are available one at a time, there si different algorithm for making heap, which is bottom up

[@Firstusee256]

Great work...

[@BackToBackSWE]

hey

[@dipeshsaili4468]

Where's the code of implementation?

[@stephan24297]

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

[@BackToBackSWE]

yes: web.cecs.pdx.edu/~sheard/course/Cs163/Doc/FullvsComplete.html

[@jameseconomy2578]

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?

[@BackToBackSWE]

sorry

[@gauthamgau6352]

Please make a video on segment trees. Thanks in advance

[@BackToBackSWE]

I probably will eventually

[@poenanster5285]

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

[@Max-zf5ot]

Heap sort code seems missing from your GH.

[@BackToBackSWE]

yeah, I have the implementation of a binary heap, but didn't implement that into heapsort.

[@Max-zf5ot]

@@BackToBackSWE No worries, anyway its not much different from actual heap implementation... Thnx

[@BackToBackSWE]

@@Max-zf5ot yeah, I may implement it soon now that you bring it up

[@rahulchowdhury9739]

You are articulate

[@sachinbhalla14]

sir your remove Method Does Not Working Properly

[@BackToBackSWE]

With what test data? Open an issue in the repo or a PR with a fix and I'll look at it.

[@sachinbhalla14]

sir suppose our input array is {8,12,7,5,14,15,18} Then The Output of Min Heap is {5,7,8,12,15,14,15,18} when we call remove Method Min Element is Deleted But Last Element is Not Deleted That is The Size Of The Array Is Not Reduced

[@BackToBackSWE]

@@sachinbhalla14 Can you open an in-depth issue on the repo? With that exact input and the output. I will investigate. I'm not home right now. - Ben

[@davidjames1684]

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

[@BackToBackSWE]

What do you mean? Also, I saw the other comment that you deleted on this video, I'll put it here for others to see your negative attitude: "Is 7 larger than every element below it, yes? You better check again! Also, in a maxheap, every element below some node does NOT need to be smaller than that node, it can be equal to or...(cut off after this, KZbin won't show it)" I made a correction for that in the teachers notes. This is a very long video and took me 5-6 hours to make...sorry for that one mistake in all of it. I guess we should just throw it all away. You are picking at tiny specifics and although you may be right...why are you attacking me? Why are you attacking someone who took their time to put out a resource to help others...for free. It is just negativity. You are only hurting yourself. If you can't learn anything here...leave. This isn't for you because you are apparently too good for this.

[@treyquattro]

@@BackToBackSWE david james is an ass, but being defensive isn't helping as an educator. He should be encouraged to stay and actually learn something. Just seize the moral high ground and let it roll off, otherwise you risk giving trolls satisfaction. Trolls who think that sorting a million ints on a 3GHz machine takes in the region of 5 seconds that is...

[@34521ful]

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

[@BackToBackSWE]

yeah

[@Divinetots]

your the best.

[@ronaktiwari6127]

Brilliant!

[@bob_jones]

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?

[@BackToBackSWE]

where? 🤕, ay screw it, it was a long video and I talked a lot haha

[@bob_jones]

@@BackToBackSWE 6:50

[@BackToBackSWE]

@@bob_jones Nice thanks

[@bob_jones]

@@BackToBackSWE No problem at all! Also, I would love if you could explain the build max heap structure in another video since you couldn't cover it in this one. I see the explanation you linked below, but it is fairly long and technical. I really enjoy your explanations as you do them quite well and in a manner simple enough that it can be understood. If you feel it is not big enough to make a video for, if you could attempt to explain it a bit more in a reply, I would sincerely appreciate it!

[@BackToBackSWE]

@@bob_jones "If you feel it is not big enough to make a video for" yeah I was thinking that. It is too nuanced. What is your question? It is pretty straight forward, go from n/2 back to index 0 and bubble items down so when you are done you have a max heap.

[@shaunzeng5996]

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

[@BackToBackSWE]

error - check pinned comment

[@zakrus]

thanks bro

[@jnanalla]

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

[@BackToBackSWE]

It is just a way to get the ejected element "out of the way". Our code knows the extent of the valid heap so to an outside consumer all is well and nothing weird is going on.

[@arnobchowdhury1804]

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

[@BackToBackSWE]

I'm in my 3rd year.

[@suryaram6874]

You the doubts in my mind!

[@davidjames1684]

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.

[@BackToBackSWE]

You must be joking.

[@davidjames1684]

Upper bounds are totally useless to me and I am a Computer Science graduate. Never used them after graduation. Not once.

[@BackToBackSWE]

@@davidjames1684 where do you work.

[@davidjames1684]

retired

[@BackToBackSWE]

​@@davidjames1684 Ok, that is my point. I'm not sure why you are attacking the content (I don't know you and you don't fully know me) but this channel is to help people prepare for Big N interviews where they will get questions like this and they need to deeply understand asymptotic bounds. What doesn't apply to you may apply to tens of thousands of other engineers. Unnecessary for the job? Yeah. I completely agree...but we aren't debating that...I'm not contesting that...I'm just out here trying to help people find work and put food on the table. See what I mean? Yeah I teach this stuff, but that doesn't mean I don't see the absurdity behind it being a measure of technical readiness for an engineering job. Basically, it is about the way interviews are done now and whether we like it or not...we have to interview to work. And I'm trying to help people find work. And pass their interviews.

[@corbbing]

See Trump? Us black people can code!

[@BackToBackSWE]

we are all human and born-into life circumstances oft determine life trajectory

[@YashHalgaonkar]

Okay, so....

[@kilroy1964]

INDEX! INDEX! INDEX!!!

[@BackToBackSWE]

hello stranger

[@kilroy1964]

@@BackToBackSWE Hi! I've been enjoying some of your lectures. While I've both studied and worked in software development, I'm rather rusty now. I've been teaching my young kid to program (his idea and he loves it!). We've been doing sorting algs, so this is a great resource. Also knowing such algs inside out, landed me my first programming job! I was given a problem that "nobody ever solves", refused a hint, and solved it in 30 seconds flat by realizing that that the solution would be similar to a radix sort. I got the job immediately! Thank you for your effort, and sharing your knowledge!

[@jameseconomy2578]

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

[@BackToBackSWE]

thanks