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

void swap(int& a, int& b)
{
	int temp = a;
	a = b;
	b = temp;
}

//1->n   0->n - 1
//2i, 2i + 1   2i + 1, 2i + 2
//n / 2   n / 2 - 1
//while(l>0)   while(l>=0)

void shift(int *a, int l, int r)
{
	int i = l, j = 2 * i + 1, x = a[i];
	while (j <= r)
	{
		if (j < r)
			if (a[j] > a[j + 1])j++;
		if (x <= a[j])break;

		a[i] = a[j];
		i = j;
		j = 2 * i + 1;
	}
	a[i] = x;
}

void initHeap(int *a, int n)
{
	int l = n/ 2 - 1;
	while (l>=0)
	{
		shift(a, l, n - 1);
		l--;
	}
}

void heapSort(int *a, int n)
{
	initHeap(a, n);
	int r = n - 1;
	while (r > 0)
	{
		swap(a[0], a[r]);
		r--;
		shift(a, 0, r);
	}
}

void khoiTaoMang(int *&a, int &n)
{
	srand(time(NULL));
	n = 20;
	a = new int[n];

	for (int i = 0; i < n; i++)
	{
		a[i] = -10 + rand() % (10 + 10 + 1);
	}
}

void xuatMang(int *a, int n)
{
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << "   ";
	}
}

int main()
{
	int *a;
	int n;

	khoiTaoMang(a, n);
	xuatMang(a, n);

	cout << endl << endl;

	heapSort(a, n);
	xuatMang(a, n);

	delete[] a;
	system("pause");
	return 0;
}