Heap Sort Algorithm

We will discuss the Heap Sort Algorithm, pseudo code, Code implementation of Heap sort in C, C++, Java, JavaScript, Python, advantages & disadvantages, and time & space complexity of Heap sort.

1. What is the Heap Sort Algorithm?

Heap Sort is one of the comparison-based sorts that uses the heap data structure.

It is a special case of selection sort. where we first find the maximum element and place the maximum element at the end. We repeat the same process for the remaining elements. Its typical implementation is not stable but can be made stable.

The heap can be built by the following two types:

• Min-Heap
• Max-Heap

1.1 Min Heap

In Min Heap, the parent node will be less than or equal to its children nodes. So, the minimum element will be at the root.

1.2 Max-Heap

In Max Heap, the parent node will be greater than or equal to its children nodes. The maximum element will be at the root.

2. Heap Sort Algorithm for Sorting in Increasing Order

Heap Sort consists of two main parts:

1. Building a heap from the input data.
2. Extracting elements from the heap and forming the sorted array.

2.1 Step-by-Step Explanation of Heap Sort

• Build a max heap from the input data.
• Repeat until the heap is empty:
  • Remove the maximum element (the root of the heap) and move it to the end of the array.
  • Reduce the size of the heap by one.
  • Heapify the root of the tree to maintain the max heap property.

2.2 Heapify function

Heapify is an important subroutine for manipulating max-heaps.

Its inputs are an array A and an index i into the array. When Heapify is called, it is assumed that the binary tree rooted at left(i) and right(i) is max heap, but that A[i] may be smaller than its children, thus violating the max-heap property.

2.3 Build Heap function

Heapify procedure is used in a bottom-up to convert an array A into a max-heap.

The elements in the subarray A[(⌊n/2⌋ + 1)…..n] are all leaves of the tree, and so each is a one-element heap to begin with. The procedure BuildHeap goes through the remaining nodes of the tree and runs Heapify on each node.

3. Pseudocode for Heapify Function

HEAPIFY(A, i)
1. le <- left(i) 
2. ri <- right(i) 
3. if (le<=heapsize) and (A[le]>A[i]) 
4. largest <- le
5. else
6. largest <- i 
7. if (ri<=heapsize) and (A[ri]>A[largest])
8. largest <- ri
9. if (largest != i)
10. exchange A[i] <-> A[largest]
11. HEAPIFY(A, largest)

3.1 Pseudocode for BuildHeap Function

BUILD_HEAP(A)
1. heapsize <- length(A) 
2. for i <- floor( length/2 ) down to 1 
3. Heapify(A, i)

3.2 Pseudocode for Heap Sort

HEAP_SORT(A) 
1.     BuildHeap(A) 
2.     for i <- length(A) down to 2 
3.         exchange A[1] <-> A[i] 
4.         heapsize <- heapsize -1 
5.         Heapify(A, 1)

4. Recurrence Relation of Heapify Function

The Recurrence Relation of Heapify() is

5. Code Implementation of Heap Sort

5.1 Heap Sort in C

#include <stdio.h>

// Function to heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i) {
    int largest = i; // Initialize largest as root
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    // If left child is larger than root
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // If right child is larger than largest so far
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // If largest is not root
    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

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

// main function to do heap sort
void heapSort(int arr[], int n) {
    // Build heap (rearrange array)
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // One by one extract an element from heap
    for (int i = n - 1; i > 0; i--) {
        // Move current root to end
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // call max heapify on the reduced heap
        heapify(arr, i, 0);
    }
}

// Function to print an array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; ++i)
        printf("%d ", arr[i]);
    printf("\n");
}

// Driver code
int main() {
    int arr[] = {6, 5, 3, 1, 8, 7, 2, 4};
    int n = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, n);

    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

5.1.1 Explanation

1. heapify: This function is used to heapify a subtree rooted at index i of size n in the given array arr.
2. heapSort: This function implements the heap sort algorithm. It first builds a max heap, then repeatedly extracts the maximum element and reconstructs the heap until the array is sorted.
3. main: In the main function, an array is initialized, heap sort is applied to it, and then the sorted array is printed.

5.2 Heap Sort in C++

#include <iostream>
using namespace std;

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 (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

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);
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {6, 5, 3, 1, 8, 7, 2, 4};
    int n = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, n);

    cout << "Sorted array: \n";
    printArray(arr, n);
    return 0;
}

5.3 Heap Sort in Java

public class HeapSort {
    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 (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;

            heapify(arr, n, largest);
        }
    }

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

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

        for (int i = n - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            heapify(arr, i, 0);
        }
    }

    public void printArray(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

    public static void main(String args[]) {
        int arr[] = {6, 5, 3, 1, 8, 7, 2, 4};
        HeapSort ob = new HeapSort();
        ob.heapSort(arr);
        System.out.println("Sorted array: ");
        ob.printArray(arr);
    }
}

5.4 Heap Sort in JavaScript

function heapify(arr, n, i) {
    let largest = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

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

function heapSort(arr) {
    const n = arr.length;

    for (let i = Math.floor(n / 2) - 1; i >= 0; i--)
        heapify(arr, n, i);

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

const arr = [6, 5, 3, 1, 8, 7, 2, 4];
heapSort(arr);
console.log("Sorted array: ", arr);

5.5 Heap Sort in Python

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left

    if right < n and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heapSort(arr):
    n = len(arr)

    # Build a maxheap.
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # Extract elements one by one.
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)

arr = [6, 5, 3, 1, 8, 7, 2, 4]
heapSort(arr)
print("Sorted array is", arr)

6. Advantages of Heap Sort

1. Guaranteed worst-case time complexity of O(n log n).
2. In-place sorting algorithm, meaning it doesn’t require additional memory proportional to the input size.
3. Heapsort has a better cache performance compared to quicksort due to its accessing memory sequentially.
4. Stable sorting algorithm.

7. Disadvantages of Heap Sort

1. Not as fast as quicksort in practice, particularly for small datasets.
2. It’s not an adaptive algorithm, meaning it doesn’t take advantage of existing order in the input.
3. More complex to implement compared to simpler algorithms like insertion sort or selection sort.
4. Not suitable for sorting linked lists.

8. Time and Space Complexity of Heap Sort

The time complexity of Heapify() is O(log n). The time complexity of BuildHeap() is O(n log n), and the overall time complexity of the heap sort is O(n log n).

9. Applications of Heap Sort

1. It sorts a nearly sorted (or k-sorted) array.
2. It sorts k largest (or smallest) elements in an array.

FAQs