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

5 жыл бұрын

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

@BackToBackSWE

4 жыл бұрын

ye

@khilarihemanshu7581

4 жыл бұрын

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

@BackToBackSWE

4 жыл бұрын

@@khilarihemanshu7581 ok

@foobars3816

3 жыл бұрын

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

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

@BackToBackSWE

5 жыл бұрын

congrats...don't make me cry 😢

@mnamaddy

Жыл бұрын

@@BackToBackSWE 😂😂

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

@BackToBackSWE

4 жыл бұрын

nice, internet friend

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

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

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

3 жыл бұрын

great

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

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

@BackToBackSWE

5 жыл бұрын

thanks. hey.

Who the heck is disliking such wonderfully crafted videos?

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

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

Amazing quality of the lecture. Thanks!

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

4 жыл бұрын

thanks.

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

@BackToBackSWE

3 жыл бұрын

sure

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.

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

4 жыл бұрын

U can do whatever u wanna do.

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

@BackToBackSWE

4 жыл бұрын

great

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

7 ай бұрын

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

Very educative and well presented. Thank you so much

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

the best youtube chanel at all times

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

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

@BackToBackSWE

5 жыл бұрын

awesome, glad it helped

very good structured explanation, thank you

He explains the best on youtube

The best explanation on the Internet. thanks

I am so lucky that I came across your channel

Awesome video man, thank you a lot!

@BackToBackSWE

4 жыл бұрын

sure

shoutout from reddit u da goat

@BackToBackSWE

5 жыл бұрын

🐐🐐🐐🐐🐐🐐

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

@BackToBackSWE

5 жыл бұрын

nice! thanks

Great video! Huge thanks!

@BackToBackSWE

4 жыл бұрын

sure

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

4 жыл бұрын

sure

Thank you, that was really clear :-).

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

4 жыл бұрын

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

@IceyBoy47

4 жыл бұрын

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

Amazing stuff!

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

@BackToBackSWE

4 жыл бұрын

hey

@kattuvasi_arun

4 жыл бұрын

@@BackToBackSWE hi, how are you

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

4 жыл бұрын

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

just came across this video and I loved it

@BackToBackSWE

4 жыл бұрын

hey

Thank you sir, very clear explanation!

@BackToBackSWE

5 жыл бұрын

sure

You are an excellent teacher.

@BackToBackSWE

5 жыл бұрын

thanks, hey

Thanks a million Ben❤it was realy helpful

@BackToBackSWE

4 жыл бұрын

ye

Great explanation!

@BackToBackSWE

2 жыл бұрын

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

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/

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

@BackToBackSWE

5 жыл бұрын

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

Brilliant!

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

4 жыл бұрын

Not very, just know summations and algebra.

@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

4 жыл бұрын

thanks

Great work...

@BackToBackSWE

5 жыл бұрын

hey

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

4 жыл бұрын

hahaha wassup! yall' Indian people are cool

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

@BackToBackSWE

4 жыл бұрын

We discuss worst case

your the best.

where is the code in description?

You are articulate

thanks bro

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

@BackToBackSWE

4 жыл бұрын

ye

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

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

2 жыл бұрын

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

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

@BackToBackSWE

4 жыл бұрын

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

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

5 жыл бұрын

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

@williamfernandesdorante6068

5 жыл бұрын

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

5 жыл бұрын

@@williamfernandesdorante6068 no it didn't haha

Where's the code of implementation?

Please make a video on segment trees. Thanks in advance

@BackToBackSWE

5 жыл бұрын

I probably will eventually

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

3 жыл бұрын

Im not sure

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

4 жыл бұрын

indeed

@holyshit922

4 жыл бұрын

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

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.

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

@BackToBackSWE

5 жыл бұрын

yeah

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

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

4 жыл бұрын

not fully sure what you mean?

@dream11tatyabichoo92

4 жыл бұрын

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

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

@BackToBackSWE

3 жыл бұрын

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

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

4 жыл бұрын

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.

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

4 жыл бұрын

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

You the doubts in my mind!

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

4 жыл бұрын

what

@dream11tatyabichoo92

4 жыл бұрын

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

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

@BackToBackSWE

5 жыл бұрын

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.

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

@BackToBackSWE

4 жыл бұрын

please see pin.

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

@BackToBackSWE

4 жыл бұрын

check pinned comment

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

@BackToBackSWE

4 жыл бұрын

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

4 жыл бұрын

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

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

4 жыл бұрын

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

4 жыл бұрын

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

@sayyidalisajjadrizavi7418

4 жыл бұрын

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

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

@BackToBackSWE

4 жыл бұрын

error - check pinned comment

Heap sort code seems missing from your GH.

@BackToBackSWE

4 жыл бұрын

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

@Max-zf5ot

4 жыл бұрын

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

@BackToBackSWE

4 жыл бұрын

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

sir your remove Method Does Not Working Properly

@BackToBackSWE

5 жыл бұрын

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

@sachinbhalla14

5 жыл бұрын

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

5 жыл бұрын

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

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

@BackToBackSWE

4 жыл бұрын

I'm in my 3rd year.

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

4 жыл бұрын

sorry

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

5 жыл бұрын

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

@bob_jones

5 жыл бұрын

@@BackToBackSWE 6:50

@BackToBackSWE

5 жыл бұрын

@@bob_jones Nice thanks

@bob_jones

5 жыл бұрын

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

5 жыл бұрын

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

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

@BackToBackSWE

5 жыл бұрын

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, KZread 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

4 жыл бұрын

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

INDEX! INDEX! INDEX!!!

@BackToBackSWE

4 жыл бұрын

hello stranger

@kilroy1964

4 жыл бұрын

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

Okay, so....

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

5 жыл бұрын

You must be joking.

@davidjames1684

5 жыл бұрын

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

@BackToBackSWE

5 жыл бұрын

@@davidjames1684 where do you work.

@davidjames1684

5 жыл бұрын

retired

@BackToBackSWE

5 жыл бұрын

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

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

@BackToBackSWE

4 жыл бұрын

thanks

See Trump? Us black people can code!

@BackToBackSWE

3 жыл бұрын

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