算法導論---堆排序

#include<iostream>

using namespace std;

void heapsort(int *a, size_t size);
void buildheap(int *a, size_t size);
void maxheapify(int *a, size_t n,size_t i);

int main()
{
	int a[11] = { -1,4,1,3,2,16,9,10,14,8,7 };
	heapsort(a, 10);
	for (size_t i = 1; i < 11; ++i)
		cout << a[i] << "  ";
	cout << endl;
	return 0;
}

void heapsort(int *a, size_t size)
{
	buildheap(a, size);
	for (size_t i = size ; i >1; --i)
	{
		std::swap(a[1], a[i]);
		--size;
		maxheapify(a, size,1);
	}
}

void buildheap(int *a, size_t size)
{
	size_t n = size;
	for (size_t i = n / 2 ; i >0; --i)
		maxheapify(a, n,i);
}

void maxheapify(int *a, size_t n,size_t i)
{
	size_t le = 2 * i , ri = 2 * i + 1;
	size_t large = i;
	if (le<=n&&a[large] < a[le])
		large = le;
	if (ri<=n&&a[large] < a[ri])
		large = ri;
	if (large != i)
	{
		std::swap(a[large], a[i]);
		maxheapify(a, n, large);
	}
}