How HeapSort works

HeapSort is a sorting method that works with the heap data structure. The method works in-place, since no further storage space (e.g. array, vector etc...) must be created here. HeapSort has an overhead of $O(nLog(n))$ in the best case, average case and worst case.

What is a heap?

A heap is a data structure which is built like a binary tree. Well, it is a binary tree that is complete. This data structure is often used for the implementation of priority queues. There are two types of heaps, the minheap and the maxheap. In the minheap, the smallest element is the root node, and the children are always larger than their parent nodes. In a maxheap, it is the other way around.

Minheap: parent nodes {'<='} child nodes

Maxheap: parent node {'>='} child node

I fibbed a bit when I said that the heap was a binary tree. The heap can be represented by a tree or an array.

Let's move on to the heap itself. To build a heap as a tree, we have to go through our list [1,4,2,5,6,8] from left to right. Here, the tree is also built from left to right. When one level of the tree is full, a new level is created. After the tree has been built, the nodes are arranged according to either minheap or maxheap. This procedure is also called heapify.

A small schematic illustration shows the construction of a heap, as well as the transformation to a maxheap.

Now we have built a maxheap. We now have the largest element as the root node and its child nodes are smaller. The child nodes of the child nodes are also smaller. This means that the deeper we move down the heap, the smaller the nodes become.

How does Heapsort work with the data structure now? HeapSort takes the root node (blue), and swaps it with the last node (blue), of the last level. After that, this node is no longer taken into account when forming the heap. Thus the root node is sorted (yellow).

A sketch, clarifies this more precisely

Implementation of HeapSort

The whole thing is repeated until the array is sorted. A small implementation in C++, we will now look at in more detail

#include <iostream> 
#include <vector>

class HeapSort
{
private:
    void swap(std::vector<int> &v, int a, int b);
public:
    HeapSort();
    ~HeapSort();
    void heapify(std::vector<int> &v, int n, int i);
    void sort(std::vector<int> &v);
};

We look at the header file "heapsort.h". Here we see the class definition of our sorting method. We have once our constructor and destructor, both are not needed here. So they are empty. We see once our heapify method, which converts the heap to a maxheap. The sort method, builds our heap, and sorts our list. The swap method, simply swaps two elements in the list.

void HeapSort::swap(std::vector<int> &v, int a, int b)
{
    int temp = v[a];
    v[a] = v[b];
    v[b] = temp;
}

If we look at the method swap, we see that we simply swap two elements in the list v, at the positions a and b. Let's come to the part where the heap is built.

void HeapSort::sort(std::vector<int> &v)
{
    int list_len = v.size();

    //Maxheap build up (bottom up) so from bottom to top.
    //(n/2) - 1 are no leaves.
    for(int i = (list_len / 2) - 1; i>=0; i--)
    {
         heapify(v, list_len, i);
    }

    //Swap root nodes with the last ones and re-heapify
    for(int i = list_len -1; i >= 0; i--)
    {
         swap(v, i, 0);
         heapify(v, i, 0);
    }
}

Let's consider the method sort. Here, the list v is passed by reference. The first thing to do is to get the length of the list. Now we build our maxheap by dividing the list in half. The first half are the nodes, which must not be treated as leaves. The other half are our child nodes or leaves. The heap is built inside the list v.

For this purpose, the following indices are defined as a formula:
Index $i$ from $n$.
Parent = $\frac{i}{2} - 1$
Left-Child = $2Parent+1$
Right-Child = $2Parent+2$

The first For loop starts at $\frac{n}{2} -1$ and goes to $0$. On each pass, the heapify method is called with the list v, the list length list_len, and the current position i. The heapify method is called on each pass. I will discuss the heapify method later.

In the lower part of the method sort, only the root is swapped with the last node from the heap. After that the rest of the heap is converted to a maxheap. This is the sorting itself.

Let's move on to the heapify method.

void HeapSort::heapify(std::vector<int> &v, int list_len, int current_pos)
{
    int largest = current_pos;
    int left = 2 * current_pos + 1;
    int right = 2 * current_pos + 2;

    //If the element at the current position is smaller than the Left child,
    //Then the Left child is larger than our Root.
    if(left < list_len && v[current_pos] < v[left]) 
    {
        largest = left;
    }

    //If our root element is smaller than the right child,
    //then the right child is larger than root.
    if(right < list_len && v[largest] < v[right])
    {
        largest = right;
    }

    //If not Maxheap, correct.
    if(largest != current_pos)
    {
        swap(v, current_pos, largest);
        heapify(v, list_len, largest);
    }
}

If we look at this method, we see that our parent largest is equal to our current position. The children left and right are twice as large as our parent. To determine the children left and right, both are incremented differently.

First we check if the index left is inside the list. And it is checked whether the element at the position left, is larger than our parent. If both are true, Parent is swapped with the left child.

Next we check if the index right is inside the list. We also check if our parent is smaller than the right child. If both are true, we swap the right child with our parent.

The swap itself takes place in the last part of the method. The affected rest heap is also processed again. After running the heapify method, we have our maxheap, as shown in the picture above.

#include "heapsort.h"


void show(std::vector<int> v)
{
    std::cout << "[";
    for(int i = 0; i < v.size(); i++)
    {
        std::cout << v[i] << ", ";
    }
    std::cout << "]" << std::endl;
}

int main()
{
    std::vector<int> v = {1, 4, 7, 1, 3, 0, -1, 53, 8};
    show(v);
    HeapSort hs = HeapSort();
    hs.sort(v);
    show(v);
    return 0;
}

In the main.cpp, a test list is created, which is first output. Afterwards our sorting method will sort the list and we will get our sorted list.

I hope I could give a little insight into the topics heaps and heapsort 😄.