【转载】图解堆排序

作者:神秘网友 发布时间:2020-10-29 02:14:04

【转载】图解堆排序

【转载】图解堆排序

原文地址:https://www.namidame.tech/heap-sort.html

所谓的堆是这样一种完全二叉树:他的每一个父结点的值都比其子结点的值大(大根堆)或小(小根堆)。我们知道,完全二叉树是每一层的结点数都达到了最大的树,每一层的结点都是先填满左边的子结点的,可以想像成一棵满二叉树截掉最右边最下边的若干个子结点。我们可以把一个数组的结构根据堆中父结点和子结点的索引关系映射成一个堆结构,然后对数组应用堆的一些操作,最后实现排序的目的。由于堆排序每一次下探树的一层,所以在处理大的数据量时能够减少操作量(二叉树的层数远比总结点数少)。

假设我们现在要排序的数组为[6,2,8,3,1,4,5,7,9],那么他的堆结构如下:
【转载】图解堆排序

根据二叉树的相关性质,我们可以知道以下规律:

大根堆:arr[i] >= arr[2 * i + 1] && arr[i] >= arr[2 * i + 2]
小根堆:arr[i] <= arr[2 * i + 1] && arr[i] <= arr[2 * i + 2]

其中若父结点在数组中的索引为i,则其左右子结点的索引分别为2i+1、2i+2。以大根堆排序为例,主要有以下步骤:

  1. 建立初始大根堆。先从最后一个父结点开始,按父结点和子结点的值关系从右往左,从下往上调整父子结点关系。
  2. 若调整后打乱了其子结点以下的结构关系,则需要重新调整其子结点以下的结点关系。重复这个步骤直到子结点关系不用调整。这时已建立起初始的大根堆。
  3. 将堆根的元素,即数组首位与数组最后一位交换,并把最后一位从接下来的操作中排除出去,即缩短数组的长度,为缩短后的堆结构继续排序。重复这个步骤,直到数组只剩下一个元素。此时数组内的值已按升序排列,排序完成。

可见每完成一次堆排序,就会将数组中最大的值移动到数组末尾,此时这个值已经在排列好后的位置,所以只需要继续将其位置之前的元素当作新的堆,重复堆排序的步骤直到整个数组有序即可。若要数组升序排列则选择大根堆,降序排列则选择小根堆。

下面来看看具体的排序步骤如何操作:

  1. 从最后一个父结点len / 2 - 1 = 3开始,调整父结点3和子结点7、8的结构,因为子结点的值9是最大的,所以将结点3、8的值互换,这就完成了第一次结点结构的调整。
    【转载】图解堆排序

  1. 继续往上调整数组中出现的上一个父结点2,由于结点2的值8已经大于子结点的值4和5,所以不作处理。
    【转载】图解堆排序

  1. 继续调整上一个父结点1,由于子结点3的值9大于父结点,交换结点1、3的值。此时结点3、7、8的结构被打乱,所以要往下调整子结点的结构,将结点3、7的值交换。
    【转载】图解堆排序
    【转载】图解堆排序

  1. 调整的最后一个父结点是根结点,由于子结点1的值大于根结点,交换结点0、1的值;交换后打乱了结点1、3、4的结构关系,需要继续调整,将结点1、3的值交换;由于此次交换没有打乱结点3、7、8的关系,所以调整结束。
    【转载】图解堆排序
    【转载】图解堆排序

  1. 现在我们已经建立了初始的大根堆,堆根的元素9便是数组中最大元素。将结点0和最尾的结点8交换,然后把结点8脱离堆结构。之后便可以把剩下的元素看成是新的堆,重复堆排序的步骤,直到整个数组有序。
    【转载】图解堆排序
  • 新的堆最后一个父结点为len / 2 - 1 = 3,注意此时数组最后一位的结点8已经不再是结点3的子结点,由于结点3、7符合要求,无需处理。
  • 继续处理数组中的上一个父结点2。父结点2也无需处理。
  • 继续处理数组中的上一个父结点1。父结点1也无需处理。

  • 继续处理数组中的上一个父结点0。交换结点0、2的值;继续交换结点2、6的值,此次调整完毕。
    【转载】图解堆排序

  • 此时结点0的值8已经是堆中最大值,将其与最后一个结点7交换,并将结点7移出堆。
    【转载】图解堆排序

  • 处理新堆的结点2,无需调整;处理上一结点1,无需处理;处理根结点,交换结点0、1。继续交换子结点1、3。
    【转载】图解堆排序

  • 处理完根结点后,交换结点0、6,将结点6移出堆。
    【转载】图解堆排序

  • 接下来重复堆排序的步骤,直到整个数组有序。
    【转载】图解堆排序
    【转载】图解堆排序
    【转载】图解堆排序
    【转载】图解堆排序

  • 实际上数组到这一步已经排序完毕了,但是算法还是会继续执行,直到数组只剩下1个元素
    【转载】图解堆排序

至此,数组已经变成升序排列。下面来看看C++的实现代码。

#include<iostream>
#include<vector>
using namespace std;
void MyHeapSort(vector<int>& nums) {
    if(nums.size() <= 1)
    {
        return;
    }

    // 交换数组两个位置的值
    auto swap_item = [](vector<int>& nums, int pos1, int pos2)
    {
        int tmp = nums[pos1];
        nums[pos1] = nums[pos2];
        nums[pos2] = tmp;
    };

    // 从某个结点pos开始调整堆
    auto heap_sort = [=](vector<int>& nums, int pos, int len)
    {
        int dad = pos;
        int son = 2 * pos + 1;
        while(son < len)
        {
            // 找出最大子结点的值
            if(son + 1 < len && nums[son + 1] > nums[son])
            {
                ++son;
            }
            if(nums[son] <= nums[dad])
            {
                return;
            }
            else
            {
                swap_item(nums, son, dad);
                dad = son;
                son = 2 * dad + 1;
            }
        }
    };
    // 先构造大根堆
    int len = nums.size();
    for(int i = len / 2 - 1; i >= 0; --i)
    {
        heap_sort(nums, i, len);
    }
    // 先交换堆根元素和最后一个元素,然后缩短数组,继续堆排序前面的数组
    for(int i = nums.size() - 1; i > 0; --i)
    {
        swap_item(nums, 0, i);
        heap_sort(nums, 0, i);
    }
};

int main()
{
    int a[9] = {6,2,8,3,1,4,5,7,9};
    vector<int> nums(a, a + 9);
    MyHeapSort(nums);
    for(auto it : nums)
    {
        cout << it << " ";  // 1 2 3 4 5 6 7 8 9
    }
    cout << endl;
}

代码中定义了一个调整堆元素的函数heap_sort,和一个交换数组两个位置上元素的函数swap_item。首先从最后一个父结点len / 2 - 1处开始向左向上调用调整函数,当调整到根结点后便建立了初始的大根堆;然后重复调用交换根元素和尾元素以及重新堆排序前面剩余元素,当堆中只剩下根结点时排序完成。

  • 堆排序只需要额外固定个数的变量来实现排序操作,变量个数不随数组规模增大而增大,所以空间复杂度为O(1)。
  • 构造大根堆和循环调整的过程都是调用heap_sort函数,该函数每次循环会将上一次的子结点当成本次的父结点,即每次下探堆的一层,数组的层数为log(n)层,每次调用该函数只减少了数组长度1,即主要操作量近似为log(n)+log(n-1)+…+log(2)+log(1),再乘以外层调用的循环次数n,即时间复杂度近似为O(nlogn),可见其对于大量数据的排序性能还是比较好的。

总结一下堆排序的主要步骤:

  1. 建立初始堆
  2. 交换堆根结点和堆尾结点,缩短数组长度
  3. 重复步骤2直到堆中只剩堆根结点,排序完成

著作权归作者所有。
商业转载请联系作者获得授权,非商业转载请注明出处。
作者: 你很德布罗意
邮箱: [email protected]
博客地址: https://www.namidame.tech/
原文地址: http://www.namidame.tech/heap-sort.html

【转载】图解堆排序相关教程

  1. C语言编写程序:从键盘输入三个数,将这三个数按从小到大排序并

    C语言编写程序:从键盘输入三个数,将这三个数按从小到大排序并输出。 实验代码: #includestdio.hint main(){double x,y,z,t;printf(请从键盘上输入三个数:);scanf(%lf%lf%lf,x,y,z);if(xy){t=x;x=y;y=t;}if(xz){t=x;x=z;z=t;}if(yz){t=y;y=z;z=t;}printf(

  2. QT 获取控件焦点

    QT 获取控件焦点 前言: 转载请附上连接,本帖原创请勿照抄。 本文通过QT过滤器来实现所有控件的获取焦点和离开焦点事件。 本文展示了两种类型的控件获取焦点和离开焦点事件的演示。 UI界面:4个LineEdit和4个Button控件 演示UI: mainwindow.h #include QRegE

  3. 快速排序详解(Java实现,包含代码实现以及算法解析)

    快速排序详解(Java实现,包含代码实现以及算法解析) 快速排序 一、快速排序的概念 二、基本算法 三、代码实现 四、快速排序算法解析 五、快速排序算法的基本性质 ? 快速排序实现简单适用于各种不同的输入数据且在一般应用中比其他排序算法都要快得多。快速

  4. 【转载】OpenCV-Python系列之ORB算法(五十一)

    【转载】OpenCV-Python系列之ORB算法(五十一) ORB是2011年ICCV上作者Rublee所提出,主要针对目前主流的SIFT或者SURF等算法的实时性进行改进。当然在实时性大为提升的基础上,匹配性能也在一定程度较SIFT与SURF算法降低。但是,在图像Two Views匹配对之间变

  5. Leetcode 26. 删除排序数组中的重复项

    Leetcode 26. 删除排序数组中的重复项 26. 删除排序数组中的重复项 解题思路 考虑到数组是有序的,故重复的元素一定是相邻的 使用双指针,慢指针指向当前遍历得到的不重复元素应该处于的位置,快指针遍历寻找下一个不重复元素 图源:https://leetcode-cn.com/

  6. PowerDesigner显示Comment注释(转载)

    PowerDesigner显示Comment注释(转载) PowerDesigner默认显示的列是Name及类型,如下图示: 现在需要显示注释列,以便使得ER图更加清晰。但是PowerDesigner勾选Comment显示没有效果,所以通过以下几步来处理: 双击表,弹出表属性对话框,切到ColumnTab,默

  7. Java数组排序:比大小+冒泡排序+选择排序+插入排序

    Java数组排序:比大小+冒泡排序+选择排序+插入排序 Java日报 部门:**大数据开发六部 姓名:cqmfx(阡陌飞絮) 日期:2020.10.25 备注:部分转自百度,CSDN,菜鸟,侵权删 一、数组介绍 二、排序 数组那些事 1、基本概念 ? 数组 (Array)是有序的元素序列。 若将

  8. leetcode:922. 按奇偶排序数组 II

    leetcode:922. 按奇偶排序数组 II 给定一个非负整数数组 A, A 中一半整数是奇数,一半整数是偶数。 对数组进行排序,以便当 A[i] 为奇数时,i 也是奇数;当 A[i] 为偶数时, i 也是偶数。 你可以返回任何满足上述条件的数组作为答案。 时空复杂度:O(N) cla