堆排序（树的结构）

忘是亡心i 2023-09-23 22:30 2阅读 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