Heap Sort

Given an array of size N. The task is to sort the array elements by completing functions heapify() and buildHeap() which are used to implement Heap Sort.

• Time : O(nlogn)
• Space : O(1)

class Solution {
public:
    //Heapify function to maintain heap property.
    void heapify(int arr[], int n, int i) {
        if(!i) return;
        int par = (i - 1) / 2;
        if(arr[par] < arr[i]) {
            swap(arr[par], arr[i]);
            heapify(arr, n, par);
        }
    }
    
    void balance(int arr[], int n, int i) {
        int left = i * 2 + 1, right = i * 2 + 2;
        if(left >= n) return;
        if(right >= n) {
            if(arr[left] > arr[i]) {
                swap(arr[left], arr[i]);
                balance(arr, n, left);
            }
        } else {
            if(arr[left] > arr[right]) {
                if(arr[left] > arr[i]) {
                    swap(arr[left], arr[i]);
                    balance(arr, n, left);
                }
            } else {
                if(arr[right] > arr[i]) {
                    swap(arr[right], arr[i]);
                    balance(arr, n, right);
                }
            }
        }
    }
    
    int pop(int arr[], int n) {
        int res = arr[0];
        swap(arr[0], arr[n]);
        balance(arr, n, 0);
        return res;
    }

public:
    //Function to build a Heap from array.
    void buildHeap(int arr[], int n) {
        for(int i = 0; i < n; i++)
            heapify(arr, i, i);
    }


public:
    //Function to sort an array using Heap Sort.
    void heapSort(int arr[], int n) {
        buildHeap(arr, n);
        
        for(int i = n - 1; i > 0; i--) {
            int ma = pop(arr, i);
            arr[i] = ma;
        }
    }
};