堆排序（树的结构）

忘是亡心i 2023-09-23 22:30 54阅读 0赞

[838. 堆排序 - AcWing题库][838. _ - AcWing]

视频（算法基础课）的：[AcWing 838. 堆排序 - AcWing][AcWing 838. _ - AcWing]

![1659a112927a464cbaeec8fd078f8b7e.png][]

**注意，每次输出堆顶元素即可，因为堆顶元素是最小的**

#include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 100010;
    
    int n, m;
    int h[N], cnt;
    
    void down(int u)
    {
        int t = u;
    
        if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
        if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    
        if (u != t)//更新最小值编号（此时t是最小值编号）
        {
            swap(h[u], h[t]);
            down(t);
        }
    }
    
    int main()
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
        cnt = n;
    
        for (int i = n / 2; i >= 1; i -- ) down(i);
    
        while (m -- )
        {
            printf("%d ", h[1]);//每次输出堆顶元素
            h[1] = h[cnt];      //把堆尾调整到堆顶
            cnt--;  //把堆尾元素调整到堆顶的位置，其实相当于把堆尾给删了（比如数组中删除最后一个数，用size-1即可，这里也是一样
            down(1);
        }
    
        cout<<' ';
    
        return 0;
    }

**从n/2开始down：****因为对于完全二叉树，小于n/2的是叶子结点，大于n/2的是根结点**

**反正到最后是输出堆顶，不管下面怎么样，堆顶都是最小的**

**这样时间复杂度是O(n)** [AcWing 838. 堆排序 - AcWing][AcWing 838. _ - AcWing]**视频第27分钟有证明**

[838. _ - AcWing]: https://www.acwing.com/problem/content/840/
[AcWing 838. _ - AcWing]: https://www.acwing.com/video/263/
[1659a112927a464cbaeec8fd078f8b7e.png]: https://img-blog.csdnimg.cn/1659a112927a464cbaeec8fd078f8b7e.png

发表评论取消回复

表情：

评论列表（有 0 条评论，54人围观）

还没有评论，来说两句吧...

相关阅读

相关堆排序（数据结构）

堆排序的建堆，大根堆和小根堆的代码实现，算法效率分析。

╰半橙微兮°/ 2024年04月23日 20:13/ 0 赞/ 119 阅读

相关算法6.堆结构、堆排序、加强堆

算法|6.堆结构、堆排序、加强堆 1.比较器的定义题意：定义一个学生类，分别实现对学生对象数组按年龄升序、按id降序、按名字的字典序、按id排序且id相同的年龄大

桃扇骨/ 2024年03月16日 09:44/ 0 赞/ 81 阅读

相关数据结构堆排序

> 堆排序基本介绍 1)堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。

小灰灰/ 2023年10月11日 10:18/ 0 赞/ 98 阅读

相关堆排序（树的结构）

[838. 堆排序 - AcWing题库][838. _ - AcWing] 视频（算法基础课）的：[AcWing 838. 堆排序 - AcWing][AcWing 838

忘是亡心i/ 2023年09月23日 22:30/ 0 赞/ 55 阅读

相关数据结构——堆排序

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。在之前的文章中已经介绍过大

悠悠/ 2023年06月23日 13:16/ 0 赞/ 98 阅读

相关树-堆结构

think： 1 今天上午学习了树中的堆结构将一些对结构的基本操作写了写，记录下来，后续继续优化。 include <stdio.h> include <

红太狼/ 2022年07月12日 03:36/ 0 赞/ 146 阅读

相关【数据结构-堆排序】堆排序 Heap Sort

　　堆排序是一种选择排序，其时间复杂度为O(nlogn)。堆的定义　　n个元素的序列\{k1，k2，…,kn\}当且仅当满足下列关系之一时，称之为堆。　　情形1：k

浅浅的花香味﹌/ 2022年06月16日 04:41/ 0 赞/ 298 阅读

相关堆结构和堆排序的Java实现

一、什么是堆堆是一棵顺序存储的完全二叉树。关于完全二叉树的定义，其实十分简单。我们都知道满二叉树，也就是所有非叶子结点的节点必有左右两个子节点的树。对于一个完全二叉树而

傷城~/ 2022年06月12日 05:27/ 0 赞/ 227 阅读

相关数据结构：堆排序

堆排序就是构建堆，然后取出堆顶元素即可代码如下 include<iostream> include<ctime> include<cs

爱被打了一巴掌/ 2022年05月31日 12:53/ 0 赞/ 479 阅读

相关数据结构-堆排序

include <iostream> using namespace std; void Sort(int a,int num,in

梦里梦外;/ 2021年11月19日 14:06/ 0 赞/ 444 阅读