七、堆与堆排序

---

 

---

堆排序与快速排序，归并排序一样都是时间复杂度为O（N*logN）的几种常见排序方法。学习堆排序前，先了解一下什么是数据结构中的二叉堆。

1.二叉堆定义

二叉堆就是完全二叉树或者近似完全二叉树

二叉堆满足二个特性：

1）父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值

2）每个节点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）

当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。

当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。

最小堆

由于其他几种堆（二项式堆，斐波那契堆等）用的较少，一般将二叉堆就简称为堆。

2.堆的存储

一般都用数组来表示堆，
i结点的父结点下标就为（i-1）/2，它的左右子节点下标分别为21+1和2i+2。如第0个结点左右子节点下标分别为1和2

3.堆的操作——插入删除

下面先给出《数据结构C++语言描述》中最小堆的建立插入删除的图解

4.排序算法

MaxHeapFixdown方法，可以实现最大堆

1. //最大堆

2. void MaxHeapFixdown(int a[], int i, int n)

3. {

4. int j, temp;

5. //这个是某某父节点

6. temp = a[i];

7. //j得到了父节点的第一个子节点的索引

8. j = 2 * i + 1;

9. while (j < n)

10. {

11. //如果j+1不超过数组长度，且右节点小于左节点，就让j指向右节点

12. if (j + 1 < n && a[j + 1] > a[j])

13. j++;

14. //如果子节点大于父节点，就跳出去

15. if (a[j] < temp)

16. break;

17. //否则的话就跟将父节点覆盖

18. a[i] = a[j];

19. //将i替换成子节点，一个是出循环之后能够实现互换的效果，一个是进入下一层比较时i是父节点

20. i = j;

21. //父节点跟子节点比较完了之后，就进入下一层比较

22. j = 2 * j + 1;

23. }

24. a[i] = temp;

25. traverse(a, 10);

26. }

MakeMaxHeap方法，制造一个堆出来

1. void MakeMaxHeap(int a[], int n)

2. {

3. //最后一个子节点的父节点开始

4. for (int i = n / 2 - 1; i >= 0; i–)

5. MinHeapFixdown(a, i, n);

6. }

MaxHeapSort方法，对堆进行排序

1. void MaxHeapSort(int a[], int n)

2. {

3. for (int i = n - 1; i >= 0; i–)

4. {

5. Swap(&a[i], &a[0]);

6. MinHeapFixdown(a, 0, i);

7. }

8. }

MinHeapFixdown是如此制造最大堆的，从1开始，小的往下沉，大的往上升

而在MinHeapSort方法中，树的最顶端是最大值，将其与最后一个互换，然后对a[0…n-1]重新恢复最大堆，继续把顶端的最大值放到后面，如此反复

注意使用最小堆排序后是递减数组，要得到递增数组，可以使用最大堆。

由于每次重新恢复堆的时间复杂度为O(logN)，共N -
1次重新恢复堆操作，再加上前面建立堆时N /
2次向下调整，每次调整时间复杂度也为O(logN)。二次操作时间相加还是O(N *
logN)。故堆排序的时间复杂度为O(N * logN)。