Sorting Algorithm study notes: Heap-sort

Prepare to have a lot of dead brain cells 🧠🧠🧠

Quick background of my motivations for writing this study notes for Heap Sort. A few weeks ago, after interviewing with multiple companies for an Android developer position, I got so frustrated because many of the questions were related to Data structure and Algorithms; I decided it was time to start reviewing this stuff.

Insertion Sorting is easy to comprehend; we can solve it with two for-loops. However, go far, go deep, as one anonymous person has said. We know that O(n square) of time complexity is garbage, so instead, we will use a better solution, HEAP-SORT; its time complexity is O(n Log n), which seems faster.

Imagine we have an array like this

4, 10, 3, 5, 1, 2, 11

Our goal is to sort it and make it like this

1, 2, 3, 4, 5, 10, 11

To use heap sort, we first must convert the array into a binary tree.

    4
   / \
  10  3
 / \ / \
5  1 2  11

Before we talk about code, let’s use a conceivable human way to sort it out first. Here is the complete conversion flow.

Look, It only took us 17 septs to sort it out…..

Overwhelming yeah?

But it only involved two patterns, Max-Heaping & Sort-Heaping

Let’s look at the graph again

Here are the particular steps that are Sort-Heaping. I marked it with square drawings. And the rest are just Max-Heaping. So, what are the definitions for both of them?

Max-Heaping: Find the current largest value inside the tree and make it the head of the node.

Sort-Heaping: After making the largest value as the head node of the tree, exchange it with the last node of the tree, so the value of the last node is guaranteed to be the biggest.

(Max-Heaping) Step.1~4 are finding the biggest value of the tree; in this case, it is 11. And we make it the head node of the tree.

(Sort-Heaping) Step.5 is after having the biggest value in the tree head node. Exchange it with the last node of the tree. Thus, making the last node the biggest of the tree.

(Max-Heaping) Step.6~7 repeats the process of finding the biggest value, but this time we will exclude the last node since in step.5, we guarantee that the last node is the biggest already.

(Sort-Heaping) Step.8 is the same concept as Step.5, but this time, we don’t exchange with the last node because it is the largest already. Instead, we exchange the node before the last node, and now we can ensure that the last two nodes are sequential.

And the rest of the steps continue until we complete the sorting process.

There you go. The concept of Heap-Sort.

Below is the code section; however, I strongly recommend you try to understand the idea first. It is much easier to draw out the steps yourself rather than code them directly.

TL;DR If you understand the idea, then the coding is the easy part.

public class HeapSortAlgo {

    public static HeapSortAlgo heapSortAlgo = new HeapSortAlgo();

    public static void main(String[] args) {
        int[] array = new int[]{4, 10, 3, 5, 1, 2, 11};
        int heapSize = array.length;
        for (int i = heapSize / 2 - 1; i >= 0; i--) {
            heapSortAlgo.maxHeaping(array, heapSize, i);
        }
        heapSortAlgo.sortHeaping(array);
    }

    private void sortHeaping(int[] array) {
        for (int i = array.length - 1; i > 0; i--) {
            System.out.println(Arrays.toString(array));
            int maxNum = array[0];
            array[0] = array[i];
            array[i] = maxNum;
            new HeapSortAlgo().maxHeaping(array, i, 0);
        }
    }

    private void maxHeaping(int[] array, int heapSize, int parentNode) {
        System.out.println(Arrays.toString(array) + "Before: " + parentNode);
        int largest = parentNode;
        int leftChildNode = 2 * parentNode + 1;
        int rightChildNode = 2 * parentNode + 2;

        if (leftChildNode < heapSize && array[leftChildNode] > array[largest]) {
            largest = leftChildNode;
        }

        if (rightChildNode < heapSize && array[rightChildNode] > array[largest]) {
            largest = rightChildNode;
        }

        if (largest != parentNode) {
            int swap = array[parentNode];
            array[parentNode] = array[largest];
            array[largest] = swap;
            maxHeaping(array, heapSize, largest);
        }
    }
}