Heap Sort

Heap Sort is an improved Selection Sort based on the (max) Heap data structure;

It divides elements into two subparts (sorted and unsorted). Heap Sort iteratively reduces the unsorted part, removing the “max” element and moving it to the sorted one until the unsorted part is empty.

First, build the Max Heap:

Then sort the heap elements:

There are two ways, use a Heap directly (with some update) or create some functions without the Heap (based on Heap code);

Let’s see the first one, “Using a Heap”.

To differentiate the sorted and unsorted parts, we need to update the Heap we created in an earlier article, let subclass it “SortingHeap,” and redefine the “Shift down” method to mark this border between unsorted and sorted parts.