Heap Sort

Heapsort was invented by John William Joseph Williams (J. W. J. Williams) in the year 1964.

Heap sort is a comparison-based sorting technique based on Binary Heap data structure called Heap Tree. It is similar to the selection sort where we first find the minimum element and place the minimum element at the beginning. Repeat the same process for the remaining elements. In this sorting algorithm, we use Max Heap to arrange list of elements in Ascending order and Min Heap to arrange list elements in Descending order.

source from imgur.com

The binary heap data structure is heap implementation that can be viewed as a complete binary tree built out of a given set of data. The heap data structure is also used in the construction of a priority queue.

A Max Heap is a complete binary tree such that for every node, key(parent) > key(child)

A Min Heap is a complete binary tree such that for every node, key(parent) < key (child)

Step-by-Step Process of heap sort

1. Build a Max Heap from the Array:
   • The first step in heap sort is to transform the input array into a max heap. A max heap is a binary tree where the value of each parent node is greater than or equal to the values of its children.
   • This is done by arranging the array such that each parent node at index i has its children at indices 2i + 1 and 2i + 2, and ensuring the heap property is satisfied starting from the lowest-level parent nodes up to the root.
   
2. Heapify the Array:
   • The process of creating a heap from an array is known as 'heapifying'.
   • Starting from the last non-leaf node (the parent of the last element), swap it with its largest child if the heap property is violated. Repeat this process moving upwards to the root of the heap.
3. Sorting the Array:
   • Once the max heap is formed, the largest element is at the root of the heap (index 0 of the array).
   • Swap this element with the last element of the heap (the last element of the array) and reduce the heap size by one (effectively removing the last element from the heap).
   • Heapify the root of the tree to ensure the max heap property is maintained.
   • Repeat this process of swapping the first element with the last, reducing the heap size, and heapifying the root until the heap size is reduced to 1.
   

Pseudo code for Heapsort

function heapSort(arr):
    n = length(arr)

    // Build a max heap from the array
    for i from n / 2 - 1 to 0:
        heapify(arr, n, i)

    // Extract elements one by one from the heap
    for i from n - 1 to 0:
        // Move current root to end
        swap arr[0] with arr[i]

        // Call max heapify on the reduced heap
        heapify(arr, i, 0)

// To heapify a subtree rooted with node i, which is an index in arr[]
function heapify(arr, n, i):
    largest = i       // Initialize largest as root
    left = 2 * i + 1  // left child
    right = 2 * i + 2 // right child

    // If left child is larger than root
    if left < n and arr[left] > arr[largest]:
        largest = left

    // If right child is larger than largest so far
    if right < n and arr[right] > arr[largest]:
        largest = right

    // If largest is not root
    if largest != i:
        swap arr[i] with arr[largest]

        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest)

// Utility function to swap two elements in an array
function swap(a, b):
    temp = a
    a = b
    b = temp

Time Complexity of the Heap Sort

• Average-case: O(n log n) - This is the typical performance experienced during sorting. Heapsort efficiently builds and maintains the heap while extracting the maximum element repeatedly.
• Worst-case: O(n log n) - The worst-case scenario occurs when the input data is already in reverse sorted order. This requires each element to be sifted up through the heap, leading to slightly slower performance compared to the average case.
• Best-case: O(n) - This rarely occurs, but if the input data is already a heap (all elements in correct order), Heapsort simply extracts the elements in descending order, resulting in optimal O(n) time complexity.