Heap Sort

This page provides introduction to Heap Sort.

Overview

Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements in ascending or descending order.

In heap sort, we need to sort non-leaf nodes first because the heap property is established and maintained through the non-leaf nodes. The heap property states that for any given node i, the value of i is either greater than (in a max heap) or less than (in a min heap) the values of its children.

Let's sort array below, with heap sort:

$$[70, 45, 75, 90, 80, 24, 2]$$

To start the heapification process, we need to identify the first non-leaf node. We can find its index using the following formula:

$$\text{N} / 2 - 1$$

Where $\text{N}$ is total number of elements in an array.

Above formula gives us first non-leaf node index as $2$. Let's proceed to heapify index $2$.

Since node at index $2$ already satisfies the heap property(i.e. value of node at index $2$ is greater than both it's child node's value), we will heapify next index $1$.

After heapifying index $=1$, tree will look like below, and recurssive heapification process now moves to index $3$, where no additional heapification is required.

Now, let's move on to heapification of last non-leaf node at index $=0$ as below:

After heapifying at index $=0$, tree will look like below and recurssive heapification process now moves to index $1$, where additional heapification is required.

After recursive heapifying at index $=1$, tree will look like below:

This concludes heapification of non-leaf node.

The next step involves recursive for each node starting from last node. Steps are as below:

• Replacing the value at the root node at index $0$ with the value of the last node.
• Reducing the heap size by 1, i.e. that node is already sorted.
• Heapifying the reduced heap from the root node at index $0$ downwards.

So let's start with replacing last node's value with root node's value and recursive heapification process excluding the last node.

• Replacing the value at the root node at index $0$ with the value of the last node.
• Reducing the heap size by 1, i.e. that node is already sorted.

• Heapifying the reduced heap from the root node at index $0$ downwards.

Let's continue the same process for index $5, 4, 3, 2, 1$, below are the snapshots of tree:

• Running the process for index $5$.

info

In the above image $90$ or $80$ didn't replace $24$ because it is already sorted and not part of the heapification process.

• Running the process for index $4$.

• Running the process for index $3$.

info

In the above image $70$ or $75$ didn't replace $2$ because it is already sorted and not part of the heapification process.

• Running the process for index $2$.

• Running the process for index $1$.

Java

public void heapify(int[] arr, int n, int i) {
  int largest = i;
  int left = 2 * i + 1;
  int right = 2 * i + 2;

  if(left < n && arr[left] > arr[largest]) {
    largest = left;
  }
  if(right < n && arr[right] > arr[largest]) {
    largest = right;
  }
  if(i != largest) {
    int temp = arr[largest];
    arr[largest] = arr[i];
    arr[i] = temp;
    heapify(arr, n, largest);
  }
}

public void heapSort(int[] arr) {
  int n = arr.length;

  // heapify non-leaf node
  for(int i = n / 2 - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  // sort
  for(int i = n - 1; i >= 0; i--) {
    heapify(arr, i, 0);
  }
}

Complexity

Let's say there are $\text{N}$ elements in an array.

Time Complexity

Building heap takes $\text{O(log N)}$ time for each element, so total time complexity is:

$$\text{O(N log N)}$$

Space Complexity

Algorithm takes no additional space.

$$\text{O(1)}$$