数据结构-堆

Eric0521 / 2024-02-24 / 原文

1.数组模拟堆

作用：

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

AcWing-838

AC代码：

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int h[N];//堆
int cnt;//堆的数量

void down(int u)
{
    int t = u;
    if (u * 2 <= cnt && h[t] > h[u * 2]) t = u * 2;//判断与左儿子的大小关系
    if (u * 2 + 1 <= cnt && h[t] > h[u * 2 + 1]) t = u * 2 + 1;//判断与右儿子的大小关系
    if (u != t)
    {
        swap(h[t], h[u]);//如果不相等就交换
        down(t);//通过递归 重新排列堆
    }
}

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i++) cin >> h[i];
    cnt=n;//数量初始化

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

    while (m--)
    {
        cout << h[1] << ' ';//输出堆顶元素
        h[1] = h[cnt];//用堆底元素覆盖堆顶元素
        cnt--;//删除堆底元素 起到删除堆顶的效果
        down(1);//重新排列
    }

    return 0;
}

AcWing-839

AC代码：