堆排序

2021/6/18 16:16:00admin4992 阅读0 点赞2 评论

#C++ #算法 #题库 #数据结构 #简单

输入一个长度为 $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;
    }
}