Heapify All The Things With Heap Sort

Vaidehi Joshi
Jul 13, 2017 · 11 min read
Heapify All Of The Things!

Heapify all the things!

Before we dive into heap sort, let’s make sure that we have heaps straight in our heads. We might remember that a heap is really nothing more than a binary tree with some additional rules that it has to follow: first, it must always have a heap structure, where all the levels of the binary tree are filled up, from left to right, and second, it must either be ordered as a max heap or a min heap. For the purposes of heap sort, we’ll be dealing exclusively with max heaps, where every parent node (including the root) is greater than or equal to the value of its children nodes.

Heap sort: a definition
The basics of heap sort
  1. 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.
  2. 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?

Alright, it’s time for my absolute favorite part of learning heap sort: drawing it out! Hooray! In order to understand what’s going on under the heap sort hood, we’ll work with a small, unsorted dataset.

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?

When I was first reading about heap sort, something about the algorithm seemed oddly familiar to me. It was only after illustrating heap sort that I realized where my feeling of déjà vu was coming from: heap sort was almost exactly like selection sort! You might remember from earlier in the series that selection sort is a sorting algorithm that sorts through a list of unsorted items by iterating through a list of elements, finding the smallest one, and putting it aside into a sorted list. It continues to sort by finding the smallest unsorted element, and adding it to the sorted list.

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.

However, as similar as they are, heap sort is much better than selection sort in one massive way: its performance! Heap sort is basically a super-improved version of selection sort. Yes, it does find the largest element in an unsorted collection and orders it at the back of the list — however, it does all of this work so much faster than selection sort would!

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

Resources

There are some really fantastic course notes and lectures on heap sorting, as well as a few good video tutorials. I did some googling so that you wouldn’t have to! Here are some great places to start if you’re interested in learning more about heap sort.

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

basecs

Exploring the basics of computer science, every Monday, for a year.

Vaidehi Joshi

Written by

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

basecs

basecs

Exploring the basics of computer science, every Monday, for a year.