C语言数据结构中堆排序的分析总结

堆排序的基本思路

堆排序（Heap Sort）是利用堆这种数据结构而设计的一种排序算法，堆排序是选择排序的一种。堆排序分为两种方法，分别是大根堆排序和小根堆排序。下面以大根堆排序为例讲解堆排序的基本思路。

1. 将初始待排序关键字序列（R1,R2....Rn）构建成大根堆，此堆为初始的无序区。
2. 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区（R1,R2,......Rn-1）和新的有序区R[n]，且满足R[1,2...n-1]<=R[n]。
3. 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区R[1..n-1]调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区（R1,R2....Rn-2）和新的有序区R[n-1,R[n]]。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

堆排序的关键点

1. 堆排序的基础是构建一个符合大根堆要求的数据结构；
2. 堆排序选取堆顶的元素与末尾元素进行交换；
3. 交换后的数组重新满足堆的性质，如有需要可以重新进行堆调整（即siftdown或siftup操作）。

堆排序的示例

示例一

假设数组arr[]={3, 5, 2, 6, 8, 4, 1, 0}，如下图所示构建大根堆：

          3
         / \
        5   2
       / \ / \
      6  8 4  1
     /
    0

将堆顶元素3与最后一个元素0交换，得到如下图所示：

          0
         / \
        5   2
       / \ / \
      6  8 4  1
     /
    3

将堆顶元素0与最后一个元素1交换，得到如下图所示：

          1
         / \
        5   2
       / \ / \
      6  8 4  3
     /
    0

此时，0和1位置交换。

将堆顶元素1与最后一个元素4交换，得到如下图所示：

          4
         / \
        5   2
       / \ / \
      6  8 0  3
     /
    1

重复上述操作，直至排序完成。

示例二

假设数组arr[]={8, 6, 4, 2, 9, 7, 5, 3, 1}，如下图所示构建大根堆：

          8
         / \
        6   7
       / \ / \
      2  9 5  3
     / \
    4   1

将堆顶元素8与最后一个元素1交换，得到如下图所示：

          1
         / \
        6   7
       / \ / \
      2  9 5  3
     / \
    4   8

此时，8和1位置交换。将堆顶元素1与最后一个元素2交换，得到如下图所示：

          2
         / \
        6   7
       / \ / \
      4  9 5  3
     /
    1

重复上述操作，直至排序完成。

总结

堆排序在时间复杂度上的表现十分优秀，时间复杂度为O(n*logn)，且空间复杂度为O(1)。但其缺点是不稳定，这是由于构建初始堆时所使用的heapify操作对相等元素的顺序会造成影响。堆排序主要应用在top k问题中，是最优解的一种。