Heaps and Heap Sort 

The main advantages of heap sort are that it sorts elements in place and produces a valid partial result while the algorithm is still running. With most other algorithms you don't get any results until they're finished or nearly finished. For instance merge sort produces no results until the start of the final merge. Heap sort starts producing results right after heapify is done, albeit in reverse order. Another advantage is that heap sort doesn't require a lot of metadata. With merge sort you must keep track of all the lists to be merged, typically using a stack. With heap sort you just need a reference to the element being sifted up or down. The sift operations use tail recursion, which means they can be done iteratively. It's not really fair to compare heap and merge with only ten elements. Try it with about 10,000 and see how they compare.

It's fun how theese child-oriented videos actually explain heap implementation better than Wikipedia article. Keep up the good work!

"Each ball is brighter than its children." Looks like those kids need some homeschooling.

Heap Sort may not be ideal when sorting is all you want to do, but this whole idea of a heap becomes invaluable when you need a data structure that allows you to always take out the smallest element quickly, but also be able to quickly modify the data in the heap in between. And often in solving some more advanced problem this is exactly what you need to do it efficiently.

you seriously need to get those robots a set of glasses, then again, it'd prevent them from taking over without them

I really like your videos about sorting. They are great visualized, and it is the first time for me understanding Heap Sort and Quick Sort XD

"Now the tree is in an illegal state" Ok who's been planting trees in israel

It's 1AM I have school tomorrow I need to finish my homework but I'm looking at CGI robots demonstrating sorting algorithms

So are these little robots actually in my computer?

I would like to see a Radix sort video.

Even before the match started I knew Heap sort would lose :( It seems like a bad sort

Heap sort is still my favorite, it's just a beautiful algorithm that works perfectly when you have to sort extremely large lists.

It might be more efficient for someone to design better eyes for your robots :P

I love how the Merge Bot had a face like "Can I leave now?" Or "Can I have my cookie now?"

I like the screens in front of their table. It makes it much easier to understand.

Different sorting compilations started showing up in my recommended, and I started watching them, confused on what they were, and now these have shown up. I’m not disappointed, just confused.

00:07 Intro to Heap/Heap Sort 02:37 Building the Heap in the first place (Heapify) 03:33 How is new elements added into a Heap 04:07 Heap Sort V.S Merge Sort Excellent Work! I felt like I haven't grown up yet! lol

I have no idea what brought me here but this seems to be a good way to spend my quarantine

I really would like to see more of those videos about sorting. I need to find a quick way to sort my books in alphabetical order.

Do smoothsort. It's along the same lines as heapsort, but does things kinda backwards so that it doesn't have to move any data if it's already sorted.

I thought h didn't exist

My teacher is now playing this in the Data Structure lesson! :)

I don't know how these sorting algorithm videos could be useful to me someday..

I just came from the halting problem video, amazed how great your physical world analogies are. The short-sighted robot that can only look closely at two balls at a time in order to compare them is another gem!

*takes out brightest ball* GET DOWN ON THE GROUND

I think the robot is cute

Not gonna lie, this actually kinda fun to watch.

heapify: one of my new favorite words

Do gravity sort That would be quite a show

Thanks! I Realy Struggled with Heap Sort. So This Helps ALOT.

I dont learn these in school, my main language isnt even English. But these, oh boi these are hella worth the watch

I think it would be more fair to also show a heapsort vs mergesort when the heapsort already has a heap structure. Both of these algorithms have O(n log n) time complexity, assuming the heapsort is executing on an already existing heap. Heaps have the advantage that extracting the min (or max for a maxheap) element is a consistent O(log n) time complexity, which is fantastic speed. This has a very high amount of use cases.

For a moment I lost respect for heapsort..

I think u should put numbers that represent the brightness on the ball, because numbers will help very much in illustrating as well as understanding the algorithms

i love seeing the winner robot just sit there waiting like *can i go home now*

YES YOUR NOT DEAD!!! I KNEW IT!

I remember watching visual versions of these (the ones that make sound that sounds like if edm music made an incest baby with a 4 year old 'composing' music) and being so confused about what was going on, and your videos make things so much easier to understand. Thank you for making these, keep up the good work!

*The time complexities are* Best: O(nlogn) Average: O(nlogn) Worst: O(nlogn) Storage: O(1)

that's racist

One of the best, visually well explained educational videos my eyes have ever watched.

…is it weird I wish I had the money to commission this channel to animate explanations of more and more sorts in this style? The graphics remind me of the old Kutoka Interactive edutainment games I used to play as a kid, like Mia Mouse. It feels like I’m hear to learn without judgement, and yet with little bits of humor thrown in. Not to mention all the sounds are soothing.

this video makes the concept of heapsort so obvious. honestly, i don't know why I was even wasting my time trying to decipher that thick, confusing textbook anymore.

I like that you made the ROBOT EYES MOVE, look at each ball when they are brought to the robot’s face. :) I noticed that. :)

I found some demonstrations regarding an algorithm called "gravity sort" but I can't seem to find any video that gives an explanation. Would you be able to point me in the direction of some resources that could explain it?

The mother The children The children's children The children's children's children

One major advantage to heapsort that's not addressed here. If you have more elements to sort than will fit into memory, you need to resort to an external merge sort. And the number of passes that the merge sort requires is dependent upon the number of runs (sorted sequences) that are already created. Assuming you can store N items in memory, the technique is to read in N items, sort them, then write out that run and repeat until you've created the initial set of runs. So each run is N items long. However, in heapsort, you read in N items, write out the lowest item and then read in the next item. If it's greater than the item just written, place the newly read item into the heap and continue. If it's less than the item just written, reduce the heap by 1 element and save the newly read item into storage. Result is that on average, using heapsort, the initial length of each run is 2N, not N. So you have about half as many runs to process with mergesort. So it runs faster.

Love these videos! Would be great if you could do some more. So much help. Thank you!!

This series is a gem

0:39 "now the tree is in an illegal state" FBI OPEN UP!

The explain is so brief and clear, thanks so much.

Why am I watching adorable robots sort bowling balls by shade

great video, i enjoy the robot animations, esp the battle at the end to help actualize sorting algorithms. Helps some of us visual-programmers understand what's going on. I get sick of algorithms easily, this helps :)

Will you be doing all of the common basic/advanced sorts?

Interesting. You don't even need a linked list or a tree to perform this sort.

always nice to see one of these

Can you do a video on gravity/bread sort? I don't understand it at all and I love your visualizations.

i dont understand why anyone would need this information but its cool and i like it

can I rest now? says the yellow bot while staring...

Why did u stopped making videos. They are so good

when i first saw this sort i thought it was a variation of the selection sort. turns out it isnt

When the person says “execute” I think of order 66 from Star Wars

0:42 "Now the tree is *_in an illegal state."_* -had me rolling-

I feel bad for the elements with no children

I like how they all have different tables

this ia actually useful. thanks for it.

It’s 1 am what am I doing

Heap Sort: You may (kinda) beat Quick Sort, but I will do even better then you, Merge Sort! Merge Sort: Let's see about that! When Merge Sort finished before Heap Sort... Merge Sort: What's taking so long, Heap Sort!!! Heap Sort: I don't know... Merge Sort: Ugh, whatever, Heap Sort.

love your videos, please keep doing them :)

quick >= merge > heap >> bubble

4:14 im just curious if you guys make the animation faster so it does it faster, is that the case?, it doesnt look like it is faster though...

Could you please specify the decision tree which is being used in heapify? I can't figure out from how the order of which ball to look at next is being determined. And when you say the lowest ball do you mean the one at the bottom or the darkest one?

Very interesting video. I cant seem to wrap my head around the heap sorting thing but hey it was fun to try

I love these videos, but I wish youtube had recommended them to me two years ago when I was taking structure and algorithms class.... but is good to remember now, since I forgot it all

Merge sort is merging pieces

The "click here" parts in the video didn't work for me. The only thing that happened was it paused and restarted the video. Can you put links to the other videos in the description?

Oh my God that's fucking genius I realize this at like a minute and a half it just blew my mind although it could be because I'm really tired right now

I would like to see a comparison between Bubble Sort and Gnome Sort. BTW: When I programm something to use gnome sort, I add a variable, at which number the algorithm was, when it starts to compare to the start. Then, when it's ready, it can go just to this index and don't compare up to the turning point.

So if making a heap already organizes the list somewhat, then what’s the point in the heap? Seems rather inefficient compared to other algorithms...

“each ball is brighter than it’s children” if you think about it it’s true in real life senses

Heap vs bubble

Through this video I understood the concept of heap sort. (I am a informatics student)

He did his best

1:01 We'll gradually move the top element downwards until it sinks down to where it belongs

"Gradually move the top element (black ball) downwards, until it sinks down to where it belongs.." What kind of racist bullshit sorting algorithm is this?

I love how these algorithims are personified as being "near-sighted". These machines aren't stupid. They don't have vision like you or me.

I feel like a chess club kid at a football practice... But the other way around... Muh Brain don't math good.

Do quick sort vs heap sort!

Heap sort just has OCD and wants to make sure everything's organized while it organizes things

Can you do Selection Sort? :)

Cool

Welcome to heaps, where no one gets married.

Life must be depressing for the near sighted robots. they have to put things inches away from their faces to see, and it takes them a while to comprehend whats infront of them, too. you shouldgive those robots some glasses, and maybe an interpereter, too. then they could compete much faster, and maybe the battles will be more interesting, too!

What if heapsort got a headstart by letting it heapify first?

The comparison between Heap Sort and Merge Sort isn't fair in my opinion. Merge Sort might be considered faster but at the expense of a significant increase of memory required

For visualizing heap maybe big/small-sized balls will do better than color - the bigger gets the lower

I need to see a tournament of every sorting algorithm in this style

Can we get an animation that uses numbers instead of colors?

I love all of your videos. They are the best! Keep up the good work

I can see the effort in making this video. Appreciate it. Thanks.

If the first step of the algo is to 'just pick the darkest ball', why can't it just do that and then pick the darkest ball of what is left... etc.