Heap Sort [Min Heap]

Heap Sort [Min Heap].cpp

#include <bits/stdc++.h>

#define MEM(a,b) memset((a),(b),sizeof(a))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MIN3(a,b,c) MIN(MIN(a,b),c)
#define MIN4(a,b,c,d) MIN(MIN(MIN(a,b),c),d)
#define In freopen("In.txt", "r", stdin);
#define Out freopen("out.txt", "w", stdout);

#define i64 long long
#define u64 long long unsigned
#define INF (1<<28)

#define sz 100

using namespace std;

int arr[sz];

void heapify(int n, int i)
{
    int root, l, r;
    root = i; // root is the smallest value position
    l = 2*i; // left child position
    r = 2*i + 1; // right child position

    // checking left child is within n and
    // either the left child is smaller
    if(l < n && arr[root] > arr[l])
        root = l;

    // checking right child is within n and
    // either the right child is smaller
    if(r < n && arr[root] > arr[r])
        root = r;

    // if root is the min value
    // then send it to the last sorted index
    // and as the current min value of 0 index is changed
    // recursively checks to build heap again
    if(root!=i)
    {
        swap(arr[root],arr[i]);
        heapify(n,root);
    }

    return;
}

void heapSort(int n)
{
    // building heaps
    for(int i=n/2; i>=0; i--)
        heapify(n,i);

    // go for every elements
    for(int i=n-1; i>0; i--)
    {
        // swap the min element (first index) and
        // the last index of unsorted
        // data
        swap(arr[0],arr[i]);
        heapify(i,0);
    }
    return;
}

void printSortedArray(int n)
{
    // printing the sorted decreasing list
    for(int i=0; i<n; i++)
    {
        if(i>0) cout << " ";
        cout << arr[i];
    }
    cout << endl;
    return;
}

int main()
{

    int n;
    while(cin >> n)
    {
        for(int i=0; i<n; i++)
            cin >> arr[i];

        heapSort(n);

        printSortedArray(n);
    }

    return 0;
}