堆排序详解

「爱情、让人受尽委屈。」 2021-09-29 19:10 546阅读 0赞

堆排序是很有难度的算法。搞懂之后就觉得，"还行吧"。

先讲个故事: 周日学校有开个实习的招聘会，没有拿到大公司offer的我，当然约上舍友走起啦。第一家，有人在面试了，那我就在旁边听下，只记得，"你会快排吗? 堆排序呢? 现在你能写出堆排序的算法??" 同为大三的面试者: "......"。

第二家，看了下，有招后台，好极了。

招python开发的吗? 用啥框架??　我用django的。很好，公司也有用django。我心里那个高兴啊。后来，聊着聊着，不对劲。面试官话里透露着一股ds的气息……我怀疑他还是学生……

他还说了公司的老板，竟然是我学校的老师，卧擦。我学校的老师竟然“兼职”去当老板了，心理多少不爽啊!! 毕竟，平时上课，教得太水了，上课浪费我时间，还老是点名。(当然少部分还是很好的)。后来换位思考，也就想通了。其实我也想当老板……谁都这样吧。

－－－－－－－－－－－－－－－－－－－－－－－－－华丽分割线－－－－－－－－－－－－－－－－－－－－－－－－－

堆分为最大堆和最小堆，其实就是完全二叉树。最大堆要求节点的元素都要不小于其孩子，最小堆要求节点元素都不大于其左右孩子，两者对左右孩子的大小关系不做任何要求，其实很好理解。有了上面的定义，我们可以得知，处于最大堆的根节点的元素一定是这个堆中的最大值。

其实我们的堆排序算法就是抓住了堆的这一特点，每次都取堆顶的元素，将其放在序列最后面，然后将剩余的元素重新调整为最大堆，依次类推，最终得到排序的序列。

### 其基本思想为(大顶堆) ###

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

下图来张教材的图，是整个堆排序的过程: 整个过程的核心就是先初始化大顶堆，将最大数(堆顶)的放到堆的最后一个, 堆长度-1, 继续调整成大顶堆，直至有序序列为len(array\_list)-1.

![1038183-20170421180601837-1333297809.png][]

堆排序前42是在42后面，排序后42在42前面，因此堆排序是不稳定的。

### 下面举例说明： ###

给定一个列表array=\[16,7,3,20,17,8\]，对其进行堆排序。

首先根据该数组元素构建一个完全二叉树，得到

![2011100413554262.jpg][]

然后需要构造初始堆，则从最后一个非叶节点开始调整，调整过程如下：

第一步: 初始化大顶堆(从最后一个有子节点开始往上调整最大堆)

![2011100413563593.jpg][]![2011100413573782.jpg][]![2011100413581745.jpg][]

20和16交换后导致16不满足堆的性质，因此需重新调整

![2011100414001028.jpg][]这样就得到了初始堆。

第二步: 堆顶元素R\[1\]与最后一个元素R\[n\]交换，交换后堆长度减一

即每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换(交换之后可能造成被交换的孩子节点不满足堆的性质，因此每次交换之后要重新对被交换的孩子节点进行调整)。有了初始堆之后就可以进行排序了。

![2011100414014182.jpg][]

第三步: 重新调整堆。此时3位于堆顶不满堆的性质，则需调整继续调整(从顶点开始往下调整)

![2011100414031854.jpg][]![2011100414052837.jpg][]

重复上面的步骤:

![2011100414061869.jpg][]![2011100414071128.jpg][]![2011100414083298.jpg][]

![2011100414092466.jpg][]![2011100414100910.jpg][]

![2011100414104814.jpg][]![2011100414111814.jpg][]![2011100414121056.jpg][]

注意了，现在你应该了解堆排序的思想了，给你一串列表，你也能写出&说出堆排序的过程。

在写算法的过程中，刚开始我是很懵比。后来终于看懂了。请特别特别注意: 初始化大顶堆时 是从最后一个有子节点开始往上调整最大堆。而堆顶元素(最大数)与堆最后一个数交换后，需再次调整成大顶堆，此时是从上往下调整的。

不管是初始大顶堆的从下往上调整，还是堆顶堆尾元素交换，每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换，交换之后都可能造成被交换的孩子节点不满足堆的性质，因此每次交换之后要重新对被交换的孩子节点进行调整。我在算法中是用一个while循环来解决的

### 开始写算法: ###

首先，我先初始化大顶堆:

1 def sift_down(array, start, end): 2     """
     3 调整成大顶堆，初始堆时，从下往上；交换堆顶与堆尾后，从上往下调整 4 :param array: 列表的引用 5 :param start: 父结点 6 :param end: 结束的下标 7 :return: 无 8     """
     9     # 当列表第一个是以下标0开始，结点下标为i,左孩子则为2*i+1,右孩子下标则为2*i+2;
    10     # 若下标以1开始，左孩子则为2*i,右孩子则为2*i+１
    11     left_child = 2*start + 1  # 左孩子的结点下标
    12     # 当结点的右孩子存在，且大于结点的左孩子时
    13     if left_child+1 <= end and array[left_child+1] > array[left_child]: 14         left_child += 1
    15     if array[left_child] > array[start]:  # 当左右孩子的最大值大于父结点时，则交换
    16         temp = array[left_child] 17         array[left_child] = array[start] 18         array[start] = temp 19 
    20     print(">>", array) 21 
    22 
    23 def heap_sort(array):  # 堆排序
    24     # 先初始化大顶堆
    25     first = len(array)//2 -1  # 最后一个有孩子的节点(//表示取整的意思)
    26     # 第一个结点的下标为０，很多博客&课本教材是从下标1开始，无所谓吧，你随意
    27     for i in range(first, -1, -1):  # 从最后一个有孩子的节点开始往上调整
    28         print(array[i]) 29         sift_down(array, i, len(array)-1)  # 初始化大顶堆
    30 
    31     print("初始化大顶堆结果:", array) 32 
    33 if __name__ == "__main__": 34     array = [16, 7, 3, 20, 17, 8] 35     print(array) 36 heap_sort(array) 37     print(array)

看下运行结果，发现有问题:

[16, 7, 3, 20, 17, 8]
    3
    >> [16, 7, 8, 20, 17, 3]
    7
    >> [16, 20, 8, 7, 17, 3]
    16
    >> [20, 16, 8, 7, 17, 3]
    初始化大顶堆结果: [20, 16, 8, 7, 17, 3]
    [20, 16, 8, 7, 17, 3]

上面代码的过程如下面4张图所示，但问题是初始化的大顶堆并不正确，当20与16交换后，算法并没有继续对以16为根结点的堆进行调整，导致17的右孩子，大于父结点16.

![2011100413554262.jpg][]![2011100413563593.jpg][]![2011100413573782.jpg][]![2011100413581745.jpg][]

于是我改进了算法，每次子结点与父结点交换后，需将以子结点为根的完全二叉树调整为大顶堆，当然，如果父结点大与左右孩子，就不需交换，当然与无须再调整为大顶堆。改进后算法如下:

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 def sift_down(array, start, end):
     2     """
     3     调整成大顶堆，初始堆时，从下往上；交换堆顶与堆尾后，从上往下调整
     4     :param array: 列表的引用
     5     :param start: 父结点
     6     :param end: 结束的下标
     7     :return: 无
     8     """
     9     while True:
    10         # 当列表第一个是以下标0开始，结点下标为i,左孩子则为2*i+1,右孩子下标则为2*i+2;
    11         # 若下标以1开始，左孩子则为2*i,右孩子则为2*i+１
    12         left_child = 2*start + 1  # 左孩子的结点下标
    13         # 当结点的右孩子存在，且大于结点的左孩子时
    14         if left_child+1 <= end and array[left_child+1] > array[left_child]:
    15             left_child += 1
    16         if array[left_child] > array[start]:  # 当左右孩子的最大值大于父结点时，则交换
    17             temp = array[left_child]
    18             array[left_child] = array[start]
    19             array[start] = temp
    20 
    21             start = left_child  # 交换之后以交换子结点为根的堆可能不是大顶堆，需重新调整
    22         else:  # 若父结点大于左右孩子，则退出循环
    23             break
    24 
    25         print(">>", array)
    26 
    27 
    28 def heap_sort(array):  # 堆排序
    29     # 先初始化大顶堆
    30     first = len(array)//2 -1  # 最后一个有孩子的节点(//表示取整的意思)
    31     # 第一个结点的下标为０，很多博客&课本教材是从下标1开始，无所谓吧，你随意
    32     for i in range(first, -1, -1):  # 从最后一个有孩子的节点开始往上调整
    33         print(array[i])
    34         sift_down(array, i, len(array)-1)  # 初始化大顶堆
    35 
    36     print("初始化大顶堆结果:", array)
    37 
    38 if __name__ == "__main__":
    39     array = [16, 7, 3, 20, 17, 8]
    40     print(array)
    41     heap_sort(array)
    42     print(array)

但是运行下，出错了，下标越界!

Traceback (most recent call last):
      File "C:/Users/Administrator/PycharmProjects/laonanhai/编程/我的堆排序.py", line 42, in <module>
        heap_sort(array)
      File "C:/Users/Administrator/PycharmProjects/laonanhai/编程/我的堆排序.py", line 35, in heap_sort
    [16, 7, 3, 20, 17, 8]
        sift_down(array, i, len(array)-1)  # 初始化大顶堆
    3
      File "C:/Users/Administrator/PycharmProjects/laonanhai/编程/我的堆排序.py", line 17, in sift_down
        if array[left_child] > array[start]:  # 当左右孩子的最大值大于父结点时，则交换
    IndexError: list index out of range
    >> [16, 7, 8, 20, 17, 3]

通过Debug知道为啥越界了

![1038183-20170423130640429-880323379.png][]

为了解决越界的问题，加个下标判定，轻松解决，oh year:

if left_child > end:
                break

初始化大顶堆代码:

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 def sift_down(array, start, end):
     2     """
     3     调整成大顶堆，初始堆时，从下往上；交换堆顶与堆尾后，从上往下调整
     4     :param array: 列表的引用
     5     :param start: 父结点
     6     :param end: 结束的下标
     7     :return: 无
     8     """
     9     while True:
    10 
    11         # 当列表第一个是以下标0开始，结点下标为i,左孩子则为2*i+1,右孩子下标则为2*i+2;
    12         # 若下标以1开始，左孩子则为2*i,右孩子则为2*i+１
    13         left_child = 2*start + 1  # 左孩子的结点下标
    14         # 当结点的右孩子存在，且大于结点的左孩子时
    15         if left_child > end:
    16             break
    17 
    18         if left_child+1 <= end and array[left_child+1] > array[left_child]:
    19             left_child += 1
    20         if array[left_child] > array[start]:  # 当左右孩子的最大值大于父结点时，则交换
    21             temp = array[left_child]
    22             array[left_child] = array[start]
    23             array[start] = temp
    24 
    25             start = left_child  # 交换之后以交换子结点为根的堆可能不是大顶堆，需重新调整
    26         else:  # 若父结点大于左右孩子，则退出循环
    27             break
    28 
    29         print(">>", array)
    30 
    31 
    32 def heap_sort(array):  # 堆排序
    33     # 先初始化大顶堆
    34     first = len(array)//2 -1  # 最后一个有孩子的节点(//表示取整的意思)
    35     # 第一个结点的下标为０，很多博客&课本教材是从下标1开始，无所谓吧，你随意
    36     for i in range(first, -1, -1):  # 从最后一个有孩子的节点开始往上调整
    37         print(array[i])
    38         sift_down(array, i, len(array)-1)  # 初始化大顶堆
    39 
    40     print("初始化大顶堆结果:", array)
    41 
    42 if __name__ == "__main__":
    43     array = [16, 7, 3, 20, 17, 8]
    44     print(array)
    45     heap_sort(array)
    46     print(array)

输出:

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

C:\Python34\python3.exe C:/Users/Administrator/PycharmProjects/laonanhai/编程/我的堆排序.py
    [16, 7, 3, 20, 17, 8]
    3
    >> [16, 7, 8, 20, 17, 3]
    7
    >> [16, 20, 8, 7, 17, 3]
    16
    >> [20, 16, 8, 7, 17, 3]
    >> [20, 17, 8, 7, 16, 3]
    初始化大顶堆结果: [20, 17, 8, 7, 16, 3]
    [20, 17, 8, 7, 16, 3]
    
    Process finished with exit code 0

### 初始化大顶堆后，已经要接近成功了。 ###

此时需要交换堆顶与堆尾，但是问题来了，堆顶肯定是array\[0\]，但堆尾呢? 因为每次交换堆顶与堆尾后，堆尾下标是会变化的啊。

为了每次交换时都能找到堆尾，我用一个循环。

# 交换堆顶与堆尾
        for head_end in range(len(array)-1, 0, -1):  # start stop step
            array[head_end], array[0] = swap(array[head_end], array[0]) # 交换堆顶与堆尾

交换堆顶与堆尾后，堆长度减一，且需从上往下调整成大顶堆。

# 交换堆顶与堆尾
        for head_end in range(len(array)-1, 0, -1):  # start stop step
            array[head_end], array[0] = swap(array[head_end], array[0]) # 交换堆顶与堆尾
            sift_down(array, 0, head_end-1)  # 堆长度减一(head_end-1)，再从上往下调整成大顶堆

自此，堆排序算法ending，你会了吗? or 你会装逼了吗?

### 堆排序代码: ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 def swap(a, b):  # 将a,b交换
     2     temp = a
     3     a = b
     4     b = temp
     5     return a,b
     6 
     7 def sift_down(array, start, end):
     8     """
     9     调整成大顶堆，初始堆时，从下往上；交换堆顶与堆尾后，从上往下调整
    10     :param array: 列表的引用
    11     :param start: 父结点
    12     :param end: 结束的下标
    13     :return: 无
    14     """
    15     while True:
    16 
    17         # 当列表第一个是以下标0开始，结点下标为i,左孩子则为2*i+1,右孩子下标则为2*i+2;
    18         # 若下标以1开始，左孩子则为2*i,右孩子则为2*i+１
    19         left_child = 2*start + 1  # 左孩子的结点下标
    20         # 当结点的右孩子存在，且大于结点的左孩子时
    21         if left_child > end:
    22             break
    23 
    24         if left_child+1 <= end and array[left_child+1] > array[left_child]:
    25             left_child += 1
    26         if array[left_child] > array[start]:  # 当左右孩子的最大值大于父结点时，则交换
    27             array[left_child], array[start] = swap(array[left_child], array[start])
    28 
    29             start = left_child  # 交换之后以交换子结点为根的堆可能不是大顶堆，需重新调整
    30         else:  # 若父结点大于左右孩子，则退出循环
    31             break
    32 
    33         print(">>", array)
    34 
    35 
    36 def heap_sort(array):  # 堆排序
    37     # 先初始化大顶堆
    38     first = len(array)//2 -1  # 最后一个有孩子的节点(//表示取整的意思)
    39     # 第一个结点的下标为０，很多博客&课本教材是从下标1开始，无所谓吧，你随意
    40     for i in range(first, -1, -1):  # 从最后一个有孩子的节点开始往上调整
    41         print(array[i])
    42         sift_down(array, i, len(array)-1)  # 初始化大顶堆
    43 
    44     print("初始化大顶堆结果:", array)
    45     # 交换堆顶与堆尾
    46     for head_end in range(len(array)-1, 0, -1):  # start stop step
    47         array[head_end], array[0] = swap(array[head_end], array[0]) # 交换堆顶与堆尾
    48         sift_down(array, 0, head_end-1)  # 堆长度减一(head_end-1)，再从上往下调整成大顶堆
    49 
    50 
    51 
    52 if __name__ == "__main__":
    53     array = [16, 7, 3, 20, 17, 8]
    54     print(array)
    55     heap_sort(array)
    56     print("堆排序最终结果:", array)

运行结果:

[16, 7, 3, 20, 17, 8]
    3
    >> [16, 7, 8, 20, 17, 3]
    7
    >> [16, 20, 8, 7, 17, 3]
    16
    >> [20, 16, 8, 7, 17, 3]
    >> [20, 17, 8, 7, 16, 3]
    初始化大顶堆结果: [20, 17, 8, 7, 16, 3]
    >> [17, 3, 8, 7, 16, 20]
    >> [17, 16, 8, 7, 3, 20]
    >> [16, 3, 8, 7, 17, 20]
    >> [16, 7, 8, 3, 17, 20]
    >> [8, 7, 3, 16, 17, 20]
    >> [7, 3, 8, 16, 17, 20]
    堆排序最终结果: [3, 7, 8, 16, 17, 20]

时间复杂度:

空间复杂度：堆排序数据交换时需要一个辅助空间，故空间复杂度是O（1）

在构建堆(初始化大顶堆)的过程中，完全二叉树从最下层最右边的非终端结点开始构建，将它与其孩子进行比较和必要的互换，对于每个非终端结点来说，其实最多进行两次比较和一次互换操作，因此整个**构建堆**的时间复杂度为: O(n)。大概需进行n/2 \* 2 = n次比较和n/2次交换。

在正式排序时，n个结点的完全二叉树的深度为⌊log2n⌋+1，并且有n个数据则需要取n-1次调整成大顶堆的操作，每次调整成大顶堆的时间复杂度为O(log2n)。因此，重建堆的时间复杂度可近似看做: O(nlogn)。

堆排序效果图:

![Sorting_heapsort_anim.gif][]

各种排序的稳定性，时间复杂度和空间复杂度总结：

![1038183-20170423220047601-777464554.png][]

上图来自:http://blog.csdn.net/hguisu/article/details/7776068

参考博客:http://www.cnblogs.com/dolphin0520/archive/2011/10/06/2199741.html

这篇博客写了好几天了。转发注明出处: [http://www.cnblogs.com/0zcl/p/6737944.html][http_www.cnblogs.com_0zcl_p_6737944.html]

转载于:https://www.cnblogs.com/0zcl/p/6737944.html

[1038183-20170421180601837-1333297809.png]: /images/20210725/eec0d225b2eb47f582a8cb11eb0ec6d6.png
[2011100413554262.jpg]: /images/20210725/2de2f0a549b746bdac06349b452f89e3.png
[2011100413563593.jpg]: https://pic002.cnblogs.com/images/2011/288799/2011100413563593.jpg
[2011100413573782.jpg]: https://pic002.cnblogs.com/images/2011/288799/2011100413573782.jpg
[2011100413581745.jpg]: /images/20210725/dd7bfe933a2d4b7496398f8c9a3a793f.png
[2011100414001028.jpg]: /images/20210725/83c7b1cf4f27437abaec68b1ffee442b.png
[2011100414014182.jpg]: /images/20210725/fd54bfe2a5194a0980a20bc79e747dc3.png
[2011100414031854.jpg]: https://pic002.cnblogs.com/images/2011/288799/2011100414031854.jpg
[2011100414052837.jpg]: /images/20210725/1e4797ac665b4c17b1915301213e559f.png
[2011100414061869.jpg]: https://pic002.cnblogs.com/images/2011/288799/2011100414061869.jpg
[2011100414071128.jpg]: https://pic002.cnblogs.com/images/2011/288799/2011100414071128.jpg
[2011100414083298.jpg]: /images/20210725/9fc5be05c639452c9beedfde5fc3f28b.png
[2011100414092466.jpg]: https://pic002.cnblogs.com/images/2011/288799/2011100414092466.jpg
[2011100414100910.jpg]: /images/20210725/c917989ba1f44b779219c4107fac8f9e.png
[2011100414104814.jpg]: https://pic002.cnblogs.com/images/2011/288799/2011100414104814.jpg
[2011100414111814.jpg]: https://pic002.cnblogs.com/images/2011/288799/2011100414111814.jpg
[2011100414121056.jpg]: /images/20210725/8c1b3e1a4ee94220a706142a2b6b3c74.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20210725/4890a4951ebe4c7fb8f35c9de3dd57f7.png
[1038183-20170423130640429-880323379.png]: /images/20210725/0850101f220848dbb1a0665912861d10.png
[Sorting_heapsort_anim.gif]: /images/20210725/c8a1908be798424592a2da674a966f76.png
[1038183-20170423220047601-777464554.png]: /images/20210725/8deee0eaeb15484fa57a36323e2143eb.png
[http_www.cnblogs.com_0zcl_p_6737944.html]: http://www.cnblogs.com/0zcl/p/6737944.html