（二叉）堆是一个数组，它可以被看成一个近似的完全二叉树。二叉堆可以分为两种形式：最大堆和最小堆。若将记录按从大到小排列，建“小”顶堆。若将记录按从小到大排，建“大”顶堆。

说明：在堆排序算法中，我们使用的是最大堆，最小堆通常用于构造优先队列。

算法分析：时间复杂度是O(nlogn)。堆排序属于原址排序：任何时候都只需要常数个额外的元素空间存储临时数据。堆排序是不稳定的排序算法。

#include
#define LEFT(i)? ? ? ? 2 * i
#define RIGHT(i)? ? 2 * i + 1

void MaxHeapAjust(int A[], int i, int len)? ? ? ? ? ? //调整节点i满足最大堆性质
{
? ? int l = LEFT(i);
? ? int r = RIGHT(i);
? ? int largest, tmp;

? ? if (l <= len && A[l - 1] > A[i - 1])
? ? {
? ? ? ? largest = l;
? ? }
? ? else
? ? {
? ? ? ? largest = i;
? ? }
? ? if (r <= len && A[r - 1] > A[largest - 1])
? ? {
? ? ? ? largest = r;
? ? }

? ? if (i != largest)
? ? {
? ? ? ? tmp = A[i - 1];? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? A[i - 1] = A[largest - 1];
? ? ? ? A[largest - 1] = tmp;

? ? ? ? MaxHeapAjust(A, largest, len);
? ? }
}

void BuildMaxHeap(int A[], int len)? ? ? ? ? ? ? ? ? ? //构造最大堆
{
? ? for (int i = len / 2; i > 0; i--)
? ? {
? ? ? ? MaxHeapAjust(A, i, len);
? ? }
}

void HeapSort(int A[], int len)? ? ? ? ? ? ? ? ? ? ? ? //堆排序
{
? ? int tmp;
? ? BuildMaxHeap(A, len);
? ? for (int i = len; i > 1; i--)
? ? {
? ? ? ? tmp = A[i - 1];
? ? ? ? A[i - 1] = A[0];
? ? ? ? A[0] = tmp;

? ? ? ? MaxHeapAjust(A, 1, i - 1);
? ? }
}

int main(void)
{
? ? int A[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
? ? HeapSort(A, 10);
? ? for (int i = 0; i < 10; i++)
? ? {
? ? ? ? printf("%d ", A[i]);
? ? }
? ? printf("\n");

? ? return 0;
}