首页 学习笔记,算法&题库,数据结构与算法

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



文章评论

目录