VIRTUALS

the virtual labs for the virtuals

0%

【AcWing算法基础】第二讲-数据结构-堆 AcWing 838. 堆排序

Posted on Edited on In , , , ,

摘要：
堆排序模板题。

题目

输入一个长度为 $n$ 的整数数列，从小到大输出前 $m$ 小的数。

输入格式
第一行包含整数 $n$ 和 $m$。

第二行包含 $n$ 个整数，表示整数数列。

输出格式
共一行，包含 $m$ 个整数，表示整数数列中前 $m$ 小的数。

数据范围

  • $1≤m≤n≤10^5$
  • $1≤数列中元素≤10^9$

输入样例：

5 3
4 5 1 3 2

输出样例：

1 2 3

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>

using namespace std;

int n, m, cnt;
const int N = 1e6 + 10;
int a[N];


void down(int i)
{
    int u = i;
    if (i * 2 <= cnt && a[i * 2] < a[u]) u = i * 2;
    if (i * 2 + 1 <= cnt && a[i * 2 + 1] < a[u]) u = i * 2 + 1;
    if (u != i)
    {
        swap(a[i], a[u]);
        down(u);
    }
}

int main()
{
    cin  >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    
    cnt = n;
    // build tree
    for (int i = cnt / 2; i > 0; -- i) 
    {
        down(i);    
    }
    
    for (; m--;)
    {
        int x = a[1];
        cout << x << " ";
        int leaf = a[cnt--];
        a[1] = leaf;
        down(1);
    }
}
1
2


理解

建堆数据结构：使用数组维护一颗二叉树，从下标 $1$ 开始，$a[i]$ 表示第 $i$ 个节点，$a[i \times 2]$ 表示其左孩子，$a[i \times 2 + 1]$ 表示其右孩子。这样，$a[N]$ 的数组恰好可以表示一颗节点数为N的二叉树。

建堆过程：初始化输入的数组表示无序堆，从第一个存在孩子的节点 $a[k]$ 开始进行节点下沉操作，其中，$k = N \div 2$. 在数组中，$k$ 右边的数不可能有孩子节点，因为超出数组边界。对 $a[k]$ 节点下沉后，依次在数组中向左遍历，进行节点下沉。

节点下沉：把 $a[k]$ 节点和其左右孩子节点比较值大小，如果 $a[k]$ 比任意一个节点小，则进行数组元素交换，在树中表现为节点和比自己小的某一个孩子节点交换位置。反之，$a[k]$ 比所有孩子节点都大，则当前堆的子结构有序，节点位置不变。最终 $a[k]$ 会找到一个树中合适的位置，该位置满足节点值比两个孩子节点的值都小，且两个孩子节点和各自的孩子节点相比依然小。

删除节点：大根堆的堆顶最小，得到最小值后，需要删除根节点。删除的方式可以复用建堆时用到的节点下沉模式，即，将某一个子节点赋值给根节点，根节点执行节点下沉。这样根节点被覆盖，再下沉到合适的位置，就完成了删除操作。注意，选取某个子节点给根节点赋值的时候，可以选数组最后一个元素，再将最后一个元素弹出序列，已达到节点替换的效果。

值得注意的点：在节点下沉过程中，需要在三个节点中两两比较，我们使用两次比较完成。第一次得到两个节点的最小值，在将最小值和第三个节点比较。

原题链接： AcWing 838. 堆排序