（二叉）堆是一个数组，它可以被看成一个近似的完全二叉树。二叉堆可以分为两种形式：最大堆和最小堆。若将记录按从大到小排列，建“小”顶堆。若将记录按从小到大排，建“大”顶堆。
说明：在堆排序算法中，我们使用的是最大堆，最小堆通常用于构造优先队列。
算法分析：时间复杂度是O(nlogn)。堆排序属于原址排序：任何时候都只需要常数个额外的元素空间存储临时数据。堆排序是不稳定的排序算法。
#include <stdio.h>
#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;
}
在Java中实现的二叉树结构