Overview

There is one more specialty sorting algorithm that we are going to consider, and it is interesting because it relies on a data structure that you already know about: heapsort! Heapsort relies on a particularly fast implementation of the method for building a heap, so we’re going to review that as well.

Basic Learning Objectives

Before class, you should be able to:

  • Explain the high-level idea of heapsort
  • Explain how a heap can be built in O(n) time

Advanced Learning Objectives

After class, you should be able to:

  • Explain the idea behind the Big-O of heapsort

Reading

You should read the following:

Checks

Submit answers to the following:

  • Given the list [4, 3, 5, 6, 1], draw out the steps for performing heapsort with both the array of the heap and the tree visualization.
  • What are the situations where heapsort is better to use than quicksort?