【C】堆的应用1 -- 堆排序

之前学习了堆，堆的一棵以顺序结构存储的完全二叉树，堆本身又氛围大根堆和小根堆，假设以大根堆为例，由于堆顶部元素是一棵二叉树里面最大的元素，所以如果每次都取堆顶的元素，那么取出的元素就是一个降序排列的序列。至此，我们发现了一个堆的特别重要的一个应用，就是堆排序。

1 问题解析

2 算法分析

3 代码

4 时空复杂度分析

（1）时间复杂度

（2）空间复杂度

1 问题解析

堆排序顾名思义就是用堆结构来实现对一个数组的排序，但是在排序过程中是不能使用堆这个数据结构的。如：有一个数组 a[] = {2, 4, 10, 9, 2, 3}，通过堆排序这个排序算法之后，数组 a 里面的数据变为了 a[] = {2, 2, 3, 4, 9, 10} 升序排列；或者是 a[] = {10, 9, 4, 3, 2, 2} 降序排列。

2 算法分析

该算法共分为两步：

1）首先对于给定的一个数组，数组里面的数据都是乱序的，既然是堆排序，我们就需要先让该数组里面的数据变成一个堆，将数组中的数据变成一个堆的算法为(这里是建大堆，建小队逻辑类似)：
这里利用的是向下调整算法，因为向下调整算法的时间效率是比向上调整算法的时间效率高的（上一篇文章有所讲解），而向下调整算法又需要其左右子树各自都是一个堆，所以首先选择最后一个节点作为孩子节点，让其父亲向下调整，这样最后一棵子树就变成了一个堆，然后再以当前孩子节点的上一个节点作为下一个孩子节点，让其父亲向下调整，直至所有的子树都被调整为了一个堆。该过程如图所示：

其本质就是从最小的一个子树建堆，然后使子树规模依次扩大，最后扩大为整棵树。

2）数组建完堆之后，由于堆顶数据总是最大的，所以我们选择让堆顶数据和最后一个节点的数据进行交换，这样最后一个数据就是有序的，然后让交换后的堆顶数据再向下建堆，但是注意这次建堆的范围应是 n - 1 个数据（n 为数组中数据的个数）；那么当前我们执行完 n - 1 次该操作之后，最大的 n - 1 个数据就会被升序的放到后 n - 1 个位置，所以就实现了升序排列。该算法如图所示：

通过理解该算法，如果要排升序的话，那么应该建大堆；排降序的话，应该建小堆。

3 代码

//升序的话，建大堆；降序的话，建小堆
//这里升序排列
void Swap(int* x, int* y)
{
  int tmp = *x;
  *x = *y;
  *y = tmp;
}

void AdjustDown(int* arr, int parent, int n)
{
  int child = 2 * parent + 1;
  while (child < n)
  {
    if (arr[child + 1] > arr[child] && child + 1 < n)
    {
      child++;
    }
    if (arr[child] > arr[parent])
    {
      Swap(&arr[child], &arr[parent]);
      parent = child;
      child = 2 * parent + 1;
    }
    else
    {
      break;
    }
  }
}

//Heap是堆的意思，Sort是排序的意思
void HeapSort(int* arr, int n)
{
  //先用所给的数组向下调整建一个堆
  for (int i = (n-1-1)/2;i >= 0;i--)
  {
    AdjustDown(arr, i, n);
  }
  //然后每次交换堆顶元素和最后一个元素，让剩余元素建大堆
  int end = n;
  while (end > 0)
  {
    //先交换
    Swap(&arr[0], &arr[--end]);
    //然后剩下元素建大堆
    AdjustDown(arr, 0, end);
  }
}

测试用例：

void Test()
{
    int arr[] = { 10, 9, 2, 4, 6, 11, 56, 20, 15, 19};
    int n = sizeof(arr) / sizeof(arr[0]);
    HeapSort(arr, n);
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
}

int main()
{
    Test();
    return 0;
}

4 时空复杂度分析

（1）时间复杂度

在上一篇文章中，我们分析了向下调整算法的时间复杂度为 O(logn) 的，而在堆排序里面共有两次循环，第一次循环会执行 n/2 - 1 次，第二次循环会执行 n 次，而这两次循环里面都嵌套了向下调整算法，所以时间复杂度为 O( (n/2 - 1)*logn + nlogn)，去除常数项和低阶项，堆排序时间复杂度就是 O(nlogn)的。