/*堆排序*/

#include 
using namespace std;

void AdjustDown(int* array, size_t size, size_t parent)
{
	size_t child = parent*2 + 1;

	while (child < size)
	{
		if (child+1 < size 
			&& array[child] < array[child+1])
		{
			++child;
		}

		if (array[child] > array[parent])
		{
			swap(array[child], array[parent]);

			parent = child;
			child = parent*2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int* array, size_t size)
{
	//建堆
	for (int i = (size-2)/2; i >= 0; --i)
	{
		AdjustDown(array, size, i);
	}

	//選數(shù)據(jù)排序
	for (size_t i = 0; i < size; ++i)
	{
		swap(array[0], array[size-i-1]);

		AdjustDown(array, size-i-1, 0);
	}
}