堆排序

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

输入格式

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

输出格式

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

数据范围

$\rm{1} \le m \le n \le {10^5}$
$\rm{1} \le 数列中的元素 \le {10^9}$

输入样例

5 3
4 5 1 3 2

输出样例

1 2 3

题解

（堆） 完全二叉树 数据结构

如何手写一个堆？

操作	代码
插入一个数	heap[++size] = x; up(size);
求集合当中的最小值	heap[1];
删除最小值	heap[1] = heap[size]; size--; down(1);
删除任意一个元素	heap[k] = heap[size]; size--; down(k); up(k);
修改任意一个元素	heap[k] = x; down(k); up(k);

up() 函数 $O(logn)$：将当前元素与其父节点进行比较，若小于，则交换；
down() 函数 $O(logn)$：将当前元素与其左、右子节点进行比较，若大于，则交换。

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int heap[N], _size;

void down(int u)
{
    int t = u;
    if(u * 2 <= _size && heap[u * 2] <= heap[t])//与左节点比较
        t = u * 2;
    if(u * 2 + 1 <= _size && heap[u * 2 + 1] <= heap[t])//与右节点比较
        t = u * 2 + 1;
    if(u != t)
    {
        swap(heap[u], heap[t]);
        down(t);//继续递归
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)//从1开始较为方便
        cin >> heap[i];
    _size = n;
    for (int i = n >> 1; i; i--)//从倒数第二层开始down即可，最后一层不需要
        down(i);
    while(m--)
    {
        cout << heap[1] << ' ';//输出堆顶（最小元素）
        heap[1] = heap[_size], _size--;//删除堆顶
        down(1);
    }
}

本题并不需要 up() 函数，故单独列出：

void up(int u)
{
    while(u / 2 && heap[u / 2] > heap[u])
    {
        swap(heap[u / 2], heap[u]);
        u /= 2;
    }
}

版权属于：字节星球/肥柴之家 （转载请联系作者授权）
原文链接：https://www.bytecho.net/archives/1819.html
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。