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

Heap Sort Algorithm

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

HeapSort()

  • Build a max heap with elements present inside array A.
  • For every element starting from the last element in A do the following.
  • The root element A[0] will contain the maximum element, swap it with this element.
  • Reduce the heap size by one and Heapify() the max heap with the last element removed.

Heapify()

  • Initialize parent index with the index of the current element.
  • Compute leftChild as 2*i+1 and rightChild as 2*i+2.
  • If the element at theleftChild is greater than the value at parent index set parent index to leftChild.
  • If the element at the rightChild is greater than the value at parent index set parent index to rightChild.
  • If the value of the parent index has changed in the last two steps, then swap parent with the current element and recursively heapify the parent index subtree. Otherwise, the heap property is already satisfied.

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:
Swap(A[5],A[0]) 4 3 5 2 1 6
Heapify() 5 3 4 2 1 6
  • Second Iteration:
Swap(A[4],A[0]) 1 3 4 2 5 6
Heapify() 4 3 1 2 5 6
  • Third Iteration:
Swap(A[3],A[0]) 2 3 1 4 5 6
Heapify() 3 2 1 4 5 6
  • Fourth Iteration:
Swap(A[2],A[0]) 1 2 3 4 5 6
Heapify() 2 1 3 4 5 6
  • Fifth Iteration:
Swap(A[1],A[0]) 1 2 3 4 5 6
Heapify() 1 2 3 4 5 6
  • Sixth Iteration:
Swap(A[0],A[0]) 1 2 3 4 5 6
Heapify() 1 2 3 4 5 6

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.

Contribute
DelftStack is a collective effort contributed by software geeks like you. If you like the article and would like to contribute to DelftStack by writing paid articles, you can check the write for us page.

Related Article - Sort Algorithm

  • Shell Sort
  • Bubble Sort Recursive