MENU

堆排序

• June 18, 2021 • Read: 2200 • 数据结构,算法,学习笔记,算法&题库

输入一个长度为 $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 国际许可协议进行许可。

Last Modified: August 29, 2023
Archives QR Code
QR Code for this page
Tipping QR Code
Leave a Comment

2 Comments
  1. 常瑞 常瑞 IP属地:天津     Windows 10+    Google Chrome

    大佬是在字节工作嘛,看好多和直接有关的东西

    1. Henry Henry     Windows 10+    Google Chrome

      @常瑞还在读本科,离工作还有段时间。