Heap: Heap Sort

In this chapter we will learn about heap sort.

To know the basic of Heap, checkout the previous chapters.

Below are the steps followed for heap sort:

1. Given an array, convert into Max heap.

2. Then take the root of the heap, and swap with the last element.

3. Then heapify the remaining tree excluding the last element.

4. Once there are no elements left to sort, the array will be sorted in ascending order.

#include <iostream>
#include <vector>
using namespace std;

void heapify(vector<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(vector<int>& arr)
{
 
    int n = arr.size();

    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(){
    vector<int> arr = { 10, 4, 8, 2, 6, 7 };

    heapSort(arr);

    for (int i = 0; i < arr.size(); ++i)
        cout << arr[i] << " ";
}

Output:

2 4 6 7 8 10

Time Complexity: O(n log n)
Auxiliary Space: O(log n)