Heap Sort

Heapify procedure can be applied to a node only if its children nodes are heapified. So the heapification must be performed in the bottom up order.

1. Build a max heap from the input data.
2. Replace the root with the last item of the heap followed by reducing the size by 1.
3. Heapify the root of tree.
4. Repeat above steps while size of heap is greater than 1.

void heapify(vector<int> &arr, int n, int i) {
    int smallest = i;
    int left = 2*i + 1;
    int right = 2*i + 2;

    // If left child is larger than root
    if (left < n && arr[left] < arr[smallest]) {
        smallest = left;
    }

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

    // If largest is not root
    if (smallest != i) {
        swap(arr[i], arr[smallest]);

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

void heapSort(vector<int> &arr) {
    // Build heap
    for (int i=arr.size()/2; i >= 0; i--) {
        heapify(s, arr.size(), i);
    }

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

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