#include <iostream>

#include <conio.h>

using namespace std;

void max_heapify(int *a, int i, int n)
/*
a : ο πίνακας.
i : κάποιο στοιχείο από την μέση του πίνακα και κάτω.
n : το πλήθος των στοιχείων όλου του πίνακα.
*/
{

int aristero_pedi, temp;

temp = a[i]; /* παίρνει το εκάστοτε στοιχείο κάτω από την μέση του πίνακα..*/

aristero_pedi = 2*i; /* */

while (aristero_pedi <= n)

	{

	if (aristero_pedi < n && a[aristero_pedi+1] > a[aristero_pedi]) /* κατι.. ΚΑΙ ..το δεξί φύλο να είναι πιο μεγαλό από το αριστερό */
		aristero_pedi = aristero_pedi+1; /* */

	if (temp > a[aristero_pedi])
		break;

	else if (temp <= a[aristero_pedi])
		{
		a[aristero_pedi/2] = aaristero_pedi];
		aristero_pedi = 2*aristero_pedi;
		}

	}

a[aristero_pedi/2] = temp;

return;

}


void heapsort(int *a, int n)

    {

        int i, temp;

        for (i = n; i >= 2; i--)

        {

            temp = a[i];

            a[i] = a[1];

            a[1] = temp;

            max_heapify(a, 1, i - 1);

        }

    }




void build_maxheap(int *a, int n)
/* n : πλήθος στοιχείων.
  a* : δείκτης στον πίνακα. */

{
int i;

for(i = n/2; i >= 1; i--)
/* i = με το μέσο του πίνακα & πάρε τον πίνακα από την μέση και κάτω.. */
/* δηλαδή πάμε στους γονέες..*/
	{
	max_heapify(a, i, n);
	}
}






int main()

{

int n, i, x;

cout<<"Πόσα στοιχεία θες να βάλεις στον πίνακα ; \n";

cin>>n;

int a[20];

for (i = 1; i <= n; i++)

	{

	cout<<"Δώσε το στοχείο  "<< (i) <<endl;

	cin>>a[i];

	}

build_maxheap(a,n);

heapsort(a, n);

cout<<"sorted output\n";

for (i = 1; i <= n; i++)

{

cout<<a[i]<<endl;

}

getch(); 

    }