Heap Sort

Heap Sort is a comparison-based sorting algorithm that works by utilizing a binary heap data structure. It was introduced by J. W. J. Williams in 1964. Heap Sort has a time complexity of O(n log n) for both the average and worst-case scenarios, making it an efficient sorting algorithm for large datasets. Heap Sort is performed in-place, but it is not a stable sort, which means that the relative order of equal elements might not be preserved.

Algorithm

The Heap Sort algorithm works by building a binary heap (either a max-heap or a min-heap) from the input data, then repeatedly extracting the maximum or minimum element and inserting it at the end of the sorted part of the array. The algorithm continues until the heap is empty, and the entire array is sorted.

The key steps in the Heap Sort algorithm are:

• Build a binary heap from the input data (either a max-heap or a min-heap).
• Repeatedly extract the maximum or minimum element from the heap and insert it at the end of the sorted part of the array.
• Continue until the heap is empty and the entire array is sorted.

Pseudocode

Here is a high-level pseudocode for the Heap Sort algorithm:

function heapSort(arr)
  buildMaxHeap(arr)
  for i = arr.length - 1 to 1
    swap arr[0] and arr[i]
    maxHeapify(arr, 0, i)
  end for
end function

function buildMaxHeap(arr)
  for i = arr.length / 2 - 1 to 0
    maxHeapify(arr, i, arr.length)
  end for
end function

function maxHeapify(arr, i, heapSize)
  largest = i
  left = 2 * i + 1
  right = 2 * i + 2
  if left < heapSize and arr[left] > arr[largest]
    largest = left
  end if
  if right < heapSize and arr[right] > arr[largest]
    largest = right
  end if
  if largest != i
    swap arr[i] and arr[largest]
    maxHeapify(arr, largest, heapSize)
  end if
end function

C++ Example

Here is a C++ implementation of the Heap Sort algorithm:

#include <iostream>

#include <vector>

void swap(int & a, int & b) {
    int temp = a;
    a = b;
    b = temp;
}

void maxHeapify(std::vector < int > & arr, int i, int heapSize) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < heapSize && arr[left] > arr[largest]) {
        largest = left;
    }

    if (right < heapSize && arr[right] > arr[largest]) {
        largest = right;
    }

    if (largest != i) {
        swap(arr[i], arr[largest]);
        maxHeapify(arr, largest, heapSize);
    }
}

void buildMaxHeap(std::vector < int > & arr) {
    for (int i = arr.size() / 2 - 1; i >= 0; i--) {
        maxHeapify(arr, i, arr.size());
    }
}

void heapSort(std::vector < int > & arr) {
    buildMaxHeap(arr);

    for (int i = arr.size() - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        maxHeapify(arr, 0, i);
    }
}

int main() {
    std::vector < int > arr = {
        12,
        11,
        13,
        5,
        6,
        7
    };
    int n = arr.size();
    heapSort(arr);
    std::cout << "Sorted array: \n";
    for (int i = 0; i < n; i++)
        std::cout << arr[i] << " ";
    std::cout << std::endl;
    return 0;
}