Published in

basecs

# Heapify all the things!

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

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

# 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

Writing words, writing code. Sometimes doing both at once.