解读堆排序算法及用C++实现基于最大堆的堆排序示例

// 用于计算下标为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);  }}

/* 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);  }}