插入一个数
heap[++size]=x; up(size);
求集合当中的最下值
heap[1];
删除最小值
heap[1]=heap[size]; size--; down(1);
删除任意一个元素
heap[k]=heap[size]; size--; up(k); down(k);
修改任意一个元素
heap[k]=x; up(k); down(k);
down函数的实现
void down(int u)
{
int t = u;
if (u * 2 <= s && h[u * 2] < h[t])t = u * 2;//左孩子存在
if (u * 2 + 1 <= s && h[u * 2 + 1] < h[t])t = u * 2 + 1;
if (u != t)
{
swap(h[u], h[t]);
down(t);
}
}
堆排
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int n, m;
int h[N], s;
void down(int u)
{
int t = u;
if (u * 2 <= s && h[u * 2] < h[t])t = u * 2;//左孩子存在
if (u * 2 + 1 <= s && h[u * 2 + 1] < h[t])t = u * 2 + 1;
if (u != t)
{
swap(h[u], h[t]);
down(t);
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> h[i];
s = n;
for (int i = n / 2; i; i--) down(i);
while (m--) {
cout << h[1] << ' ';
h[1] = h[s]; s--; down(1);
}
}
标签:,int,up,down,--,heap,size
From: https://www.cnblogs.com/windzhao6/p/18327273