AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

堆和堆排序笔记

作者: 作者的头像   nihaotian ,  2019-07-10 20:19:37 ,  所有人可见 ,  阅读 2094


4


6

如何手写一个堆?

堆支持的操作:

  1. 插入一个数

  2. 求集合当中的最小值

  3. 删除最小值

  4. 删除任意一个元素

  5. 修改任意一个操作

后面两个操作无法直接用STL实现。

堆本质上是一棵完全二叉树。以小根堆为例,其每个点都是小于等于左右子节点的,根节点就是整个树的最小值。

堆的存储方式:用一维数组存储,设根节点的下标是x,则左儿子是2x,右儿子是2x+1.

往下调整与往上调整:
如果某个数变大了,就要把它往下移,直到不能下移为止;反之,则要往上移。

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]; //修改任意一个元素

题目描述

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

具体实现

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;

int n,m;
int h[N],size;

void down(int u)
{
    int t = u;
    if(u*2 <= size && h[u*2] < h[t]) t = u*2;
    if(u*2 + 1 <= size && h[u*2 + 1] < h[t]) t = u*2 + 1;
    if(u != t)
    {
        swap(h[u],h[t]);
        down(t);
    }
}

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

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i<=n;i++) scanf("%d",&h[i]);
    size = n;

    for(int i = n/2;i;i--) down(i);

    while(m--)
    {
        printf("%d ",h[1]);
        h[1] = h[size];
        size--;
        down(1);
    }

    return 0;
}

2 评论


用户头像
剑指Rejection   2020-03-05 12:56         踩      回复

支持


用户头像
k8s   2020-03-04 20:39         踩      回复

1024


App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息