这里的算法实现使用的是最大堆，首先来解决由数组建立最大堆的问题:
// 用于计算下标为i的节点的两个子节点的下标值
#define LEFT(i) (2 * (i) + 1)
#define RIGHT(i) (2 * ((i) + 1))
/* 此函数把一颗二叉树中以node为根的子树变成最大堆。
* 注意: 使用的前提条件是 node节点的左右子树(如果存在的话)都是最大堆。
* 这个函数是整个算法的关键。
*/
void max_heapify(int heap[], int heap_size, int node)
{
// 这里先不考虑整数溢出的问题
// 先把注意力放在主要的功能上
// 如果数据规模够大,int类型必然会溢出
int l_child = LEFT(node);
int r_child = RIGHT(node);
int max_value = node;
if (l_child < heap_size && heap[l_child] > heap[max_value])
{
max_value = l_child;
}
if (r_child < heap_size && heap[r_child] > heap[max_value])
{
max_value = r_child;
}
if (max_value != node)
{
swap_val(heap + node, heap + max_value);
// 之后还要保证被交换的子节点构成的子树仍然是最大堆
// 如果不是这个节点会继续"下沉"，直到合适的位置
max_heapify(heap, heap_size, max_value);
}
}
/* 将一个数组构造成最大堆
* 自底向上的利用max_heapify函数处理
*/
void build_max_heap(int heap[], int heap_size)
{
if (heap_size < 2)
{
return;
}
int first_leaf = heap_size >> 1;//第一个叶子节点的下标
int i;
// 从最后一个非叶子节点开始自底向上构建，
// 叶子节点都看作最大堆，因此可以使用max_heapify函数
for (i = first_leaf - 1; i >= 0; i--)
{
max_heapify(heap, heap_size, i);
}
}
函数max_heapify将指定子树的根节点"下沉"到合适的位置, 最终子树变成最大堆， 该过程最坏时间复杂度为O(logn)O(logn)。函数build_max_heap自底向上的调用max_heapify, 最终整个数组满足最大堆，迭代过程的复杂度为O(nlogn)O(nlogn)， 因此整个函数的最坏时间复杂度也是O(nlogn)O(nlogn)。 而如果当前数组已经是最大堆了，例如数组原本是降序排列的， 那么max_heapify过程的时间复杂度就是O(1)O(1), 此时build_max_heap的时间复杂度是O(n)O(n)，这是最好的情况。
接着实现堆排序过程：
/* heap sort 主函数
*/
void heap_sort(int heap[], int heap_size)
{
if (heap == NULL || heap_size < 2)
{
return;
}
//构建最大堆
build_max_heap(heap, heap_size);
int i;
for (i = heap_size - 1; i > 0; i--)
{
/* 把当前树的根节点交换到末尾
* 相当于取出最大值，树的规模变小。
* 交换后的树不是最大堆，但是根的两颗子树依然是最大堆
* 满足调用max_heapify的条件。之所以这样交换，
* 是因为用max_heapify处理时间复杂度较低，
* 如果不交换而直接"取出"heap[0], 此处可能要使用
* build_max_heap重新建立最大堆，时间复杂度较大
*/
swap_val(heap, heap + i);
heap_size--;
//维护最大堆
max_heapify(heap, heap_size, 0);
}
}
