Heap Sort

1. Heap Sort Algorithm
2. Heap Sort Example
3. Heap Sort Algorithm Implementation
4. Heap Sort Algorithm Complexity

Heap sort is a comparison-based sorting algorithm. It gets its name from the heap data structure used in the algorithm. Heap is a binary tree based special data structure. It has the following two properties:

• It is a complete binary tree with all levels filled except the last one. The last one may be partially filled, but all the nodes are as far left as possible.
• All the parent nodes are smaller/larger than their two children nodes. If they are smaller, heap is called min-heap, and if larger, then the heap is called max-heap. For a given index i, the parent is given by (i-1)/2, the left child is given by (2*i+1) and the right child is given by (2*i+2).

Heap sort works in a manner quite similar to selection sort. It selects the maximum element from the array using max-heap and puts it in its position at the back of the array. It makes use of a procedure called heapify() to build the heap.

Heap Sort Algorithm

Let us assume that we have an unsorted array A[] containing n elements.

HeapSort()

Heapify()

Heap Sort Example

Suppose we have the array: (5, 3, 4, 2, 1, 6). We will sort it using the heap sort algorithm.

After building the heap, we get the array as: (6 3 5 2 1 4).

• First Iteration:

• Second Iteration:

• Third Iteration:

• Fourth Iteration:

• Fifth Iteration:

• Sixth Iteration:

We get the sorted array as : (1,2,3,4,5,6)

Heap Sort Algorithm Implementation

#include <bits/stdc++.h>
using namespace std;

void heapify(int arr[], int n, int i) {
  int parent = i;
  int leftChild = 2 * i + 1;
  int rightChild = 2 * i + 2;

  if (leftChild < n && arr[leftChild] > arr[parent]) parent = leftChild;

  if (rightChild < n && arr[rightChild] > arr[parent]) parent = rightChild;

  if (parent != i) {
    swap(arr[i], arr[parent]);
    heapify(arr, n, parent);
  }
}

void heapSort(int arr[], int n) {
  for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);

  for (int i = n - 1; i >= 0; i--) {
    swap(arr[0], arr[i]);
    heapify(arr, i, 0);
  }
}

int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  heapSort(arr, n);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Heap Sort Algorithm Complexity

Time Complexity

• Average Case

The height of a complete binary tree with n elements is at max logn. So, the heapify() function can have a maximum of logn comparisons when an element moves from root to leaf. The build heap function is called for n/2 elements making the total time complexity for the first stage n/2*logn or T(n) = nlogn.

HeapSort() takes logn worst time for each element, and n elements are making its time complexity also nlogn. Both the time complexity for building heap and heap sort is added and gives us the resultant complexity as nlogn. Hence, the total time complexity is of the order of [Big Theta]: O(nlogn).

• Worst Case

The worst-case time complexity is [Big O]: O(nlogn).

• Best Case

The best-case time complexity is [Big Omega]: O(nlogn). It is the same as the worst-case time complexity.

Space Complexity

Space Complexity for heap sort algorithm is O(1) because no extra memory other than temporary variables is required.