Sorting Algorithms: Heapsort

Developed in 1964 by J.W.J. Williams, Heapsort uses the heap data structure, a specialized tree structure.

"Divider" written & performed by Chris Zabriskie

[dlwatib]

Heapsort works by *efficiently* deciding which of the unsorted elements is largest, then swapping that element with the element at the end of the list (an array, aka vector) and then shortening its unsorted list by one and repeating the process.

The trick is in *efficiently* deciding which element is largest at each step. The unsorted elements are first arranged and then maintained in what is called a heap or priority queue with the constraint that the element at location N is always (recursively) larger than its two children at 2N and 2N+1. Implicitly the heap forms a binary tree with the largest element on top (the left, location 1). Each route down through the tree from the top is sorted in descending order.

When the top element is swapped with the one at the end of the list, the new top is usually small (because it used to be at the end of the list), but it isn't very hard to maintain the heap. Just compare and swap location 1 with the larger of the elements in locations 2 or 3, then repeat with N, 2N and 2N+1 until you don't need to make any more swaps to get the larger ones higher in the tree (lower locations) than the new (small) one. Then once again your largest unsorted element is in location 1 and you can swap it for the end of the list, shorten the list by one and repeat until the unsorted list is down to one element.

The advantage of a heap over a conventional binary tree is that the tree automatically remains balanced throughout the process. Heapsort has much in common with merge sorts because each of the paths through the heap forms a (reverse) ordered list.

[mikeynjs]

It would've been nice if you had assigned different colors to each heap so you could see exactly what's going on.

[stevenclark]

It's interesting watching the poisson noise form as the density of the distribution in the 5000 item one increases.

[adrianfrauca]

Let me just say that the explanation of the sorting method at the beginning didn't tell me anything and failed in actually explaining what a heap is or what the process consists of.

[SuperfieldCrUn]

Heap sort can be viewed as a "work smarter, not harder" take on selection sort (that is, max selection sort, where you find each successive largest value and place it at the end of the list) and perhaps bubble sort. All of them, after a single iteration, have extended the sorted portion of the list by 1, this sorted portion is at the end of the list, and all elements in the sorted portion are in their final location. Where heap sort comes out so far ahead of those algorithms is in how it finds the next largest element. Selection sort accomplishes this by looking at each and every unsorted element and seeing if it is higher than the currently known highest element. Bubble sort accomplishes this by repeatedly moving forward larger elements - "survival (or advancement) of the fittest", you might say, and every unsorted element has to be put to the test every iteration. But heap sort pulls the largest element up extremely quickly and with minimal effort. Larger values naturally make leaps and bounds up the heap, and each time an element needs to be sifted down to rebuild the heap, a single comparison eliminates half of the elements that it could potentially be compared to. Even extremely large lists like 1, 000, 000 would only require about 20 comparisons total in a single iteration at maximum, as compared to the hundreds of thousands required by selection or bubble sort. The only downside is the upfront work needed to construct the heap in the first place, but this only becomes a problem with very small lists that don't need it. For any list of decent size, the work will be worth it.

[BBand]

Heapsort is frustrating, because it was finished, but decided to keep swapping anyway! The OCD in me was screaming "STOP! YOU GOT IT!"

[MasterOfTheChainsaw]

Judging from what I can see, it looks like heap sort is pretty slow with small datasets, not being much faster than even bubble sort, but at large datasets it's far more efficient than simple algorithms like bubble sort? How does heap sort compare to, say, quick sort, when it comes to small datasets like 25, as well as large datasets like 5000?

[DiamondSane]

Thats my favorite, I can look this forever.
And music is very well. I also appreciated, you have a different soundtrack for every algorithm.

[realflow]

should combine heapsort with another sorting type.. Would be interesting to see...

[brianxx]

I would expect that reversing the heap (bigger values on the right instead of the left) would noticeably reduce the number of movements required.

[davidjames]

21x comparisons and 11x movements (for 5, 000 elements to heapsort), is not what I would call efficient. That is a LOT of comparisons and a LOT of moving stuff around, just to maintain the heap property. Also, heapsort is not stable (order preserving for same value input items), but can be made stable with some extra effort.

[LimeEffy]

When i look at it, heapsort actually has constant sorting speed.

[alspezial]

from what i see it looks like selection sort with extra steps, but what the extra steps actually do doesn't appear to me

[RickertBrandsen]

How are these animations are made? does anyone know?

[simonthiesen]

You got istantly a Abbo from as i saw that you uploadet 3 sorting videos in on moth.