basecs
Published in

basecs

Heapify All The Things With Heap Sort

Heapify All Of The Things!

Heapify all the things!

Heap sort: a definition
The basics of heap sort
  1. To start, we have an unsorted array. The first step is to take that array and turn it into a heap; in our case, we’ll want to turn it into a max heap. So, we have to transform and build a max heap out of our unsorted array data. Usually, this is encapsulated by a single function, which might be named something like buildMaxHeap.
  2. Once we have our array data in a max heap format, we can be sure that the largest value is at the root node of the heap. Remember that, even though the entire heap won’t be sorted, if we have built our max heap correctly and without any mistakes, every single parent node in our heap will be larger in value than its children. So, we’ll move the largest value — located at the root node — to the end of the heap by swapping it with the last element.
  3. Now, the largest item in the heap is located at the last node, which is great. We know that it is in its sorted position, so it can be removed from the heap completely. But, there’s still one more step: making sure that the new root node element is in the correct place! It’s highly unlikely that the item that we swapped into the root node position is in the right location, so we’ll move down the root node item down to its correct place, using a function that’s usually named something like heapify.

Have you ever looked under heap sort’s hood?

Implementing heap sort, part 1
Implementing heap sort, part 2
Implementing heap sort, part 3
Implementing heap sort, part 4
Implementing heap sort, part 5
Heap sort visualized, Wikimedia Commons

Heap sort: what is it good for?

It turns out that heap sort is a lot like selection sort in its logic: both algorithms find either the smallest or largest element, “select” it out, and put that item in its correct location in the sorted list.

Heap sort: kind of like selection sort, but so much better!
Understanding heap sort’s time complexity
How does heap sort stack up?

Resources

  1. Introduction to Algorithms: Heap Sort, MIT
  2. Algorithms: Heap Sort, Professor Ching‐Chi Lin
  3. Heap sort, Growing with the Web
  4. Heap sort in 4 minutes, Michael Sambol
  5. Heap sort: Max heap, strohtennis

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store