《大话数据结构笔记》--堆排序

深藏阁楼爱情的钟 2023-02-15 12:39 38阅读 0赞

**堆**是具有如下性质的**完全二叉树**:  
每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆（如9-7-2左图所示）；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆（如9-7-2右图所示）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDAyOTcwMw_size_16_color_FFFFFF_t_70]  
深度为k的满二叉树的结点数 n < 2 k − 1 n < 2^k -1 n<2k−1, 如果对一课有n个结点的完全二叉树的结点按层序编号，对于任意结点 i ( 1 < = i < = n ) i(1<= i <= n) i(1<=i<=n)，有如下：  
**如果 i = 1 i=1 i=1，则结点 i i i是二叉树的根，无双亲，如果 i > 1 i > 1 i>1， 则其双亲是结点\[i/2\]， 其中\[\]表示下取整。其左孩子为结点 2 i 2i 2i, 右孩子结点为 2 i + 1 2i+1 2i\+1**  
如果将图9-7-2的大顶堆和小顶堆用层序遍历存入数组，数组的索引满足上面的关系，如下图所示  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDAyOTcwMw_size_16_color_FFFFFF_t_70 1]

## 堆排序算法 ##

**堆排序**是利用堆进行排序的方法，基本思想是**将待排序的序列构成一个大顶堆，此时，整个序列的最大值就是堆顶的根结点，将它移走（将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构成一个堆，这样就得到n个元素的次小值。如此反复执行，便得到一个有序序列。**  
下面用例子来模拟整个过程  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDAyOTcwMw_size_16_color_FFFFFF_t_70 2]

1.  上图为一个大顶堆，90位最大值，将90与20（末尾元素互换），那么20为根结点，90成了整个堆序列的最后一个元素
2.  对根结点20进行调整，先与其最大的子结点80交换，在与最大的子结点50交换，使得除最后一个元素90以外的结点满足大顶堆的定义，如下图  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDAyOTcwMw_size_16_color_FFFFFF_t_70 3]
3.  再将30与80互换，按照2步骤，生成满足如上定义的最大顶堆的定义，反复1， 2， 3步骤…  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDAyOTcwMw_size_16_color_FFFFFF_t_70 4]  
    那么在实现堆排序的过程中，最核心的要考虑两个问题:

*  如何由一个无序序列构成一个堆？
 *  如果在输出堆顶元素后，如何调整剩余元素称为一个新的堆？

假设我们要排序的序列是\[50, 10, 90, 30, 70, 40, 80, 60, 20\]，序列的长度为9，那么根据如果结点编号为 i i i， 其右孩子结点编号为 2 i 2i 2i, 右孩子结点编号为 2 i + 1 2i+1 2i\+1

对应的二叉树为下图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDAyOTcwMw_size_16_color_FFFFFF_t_70 5]  
将待排序的序列构建称为一个大顶堆，就是从下往上、从右往左，将每个非终端结点（非叶结点，有孩子的）当做根结点，将其和其子树调整成大顶堆  
也就是将图9-7-5中30, 90, 10, 50的结点调整，构成大顶堆的过程。用python 语言实现

def heap_adjust(nums, i, length):
        # 数组nums为[0, 50, 10, 90, 30, 70, 40, 80, 60,20]
        temp = nums[i]
        # 遍历沿着结点i的孩子结点向下筛选
        j = 2 * i  # 右孩子结点编号
        while j <= length:
            if j < length and nums[j] < nums[j+1]:
                # 如若右孩子大于左孩子
                j += 1
            if temp > nums[j]:
                break
            # 将较大的子结点赋值给根结点，注意不是交换，还需再进行检测下一层子结点
            nums[i] = nums[j]
            i = j
            j *= 2
        nums[i] = temp
    
    def heap_sort(nums, length=9):
        # 注意二叉树的结点编号为数组索引加1,为了方便计算，我们在数组索引为0处增加了0元素
        length = len(nums)
        for i in range(length//2, 0, -1):
            heap_adjust(nums, i, length)

下面实现排序的过程

for i in range(length, 0, -1):
            swap(nums, 1, i)  # 将堆顶记录（根结点）和当前未经排序的子序列的最后一个记录交换
            heap_adjust(nums, 1, i-1)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDAyOTcwMw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200605130356433.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDAyOTcwMw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDAyOTcwMw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200605140940853.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDAyOTcwMw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDAyOTcwMw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200605141629727.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDAyOTcwMw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDAyOTcwMw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200605141921150.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDAyOTcwMw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDAyOTcwMw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200605142702801.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDAyOTcwMw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDAyOTcwMw_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200605144758695.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDAyOTcwMw==,size_16,color_FFFFFF,t_70