堆

堆

堆是一种有效的完全二叉树结构，常用于实现优先队列。最大堆和最小堆分别保证根节点为最大或最小元素，常用于排序、图算法和合并有序数据等问题

#include <iostream>
#include <algorithm>
using namespace std;

//堆是完全二叉树
//插入一个数(在最后插入一个数，并把这个数往上移)
//heap[++size] = x; up(size);
//求集合中的最小值
//heap[1]
//删除最小值(把最小的数用最后一位数覆盖掉，并把这个数往下移)
//heap[1] = heap[size]; size--; down(1);
//删除任意一个元素(down和up只会执行一个，所以可以都写)
//heap[k] = heap[size]; size--; down(k); up(k)
//修改任意一个元素
//heap[k] = x; down(k); up(k);

//x的儿子为2 * x和2 * x + 1
const int N = 100010;

int n, m;
//为了避免关键字重复，把size改为cnt
int h[N], cnt;

void down(int u)
{
	//t代表当前节点
	int t = u;
	//左儿子
	if (u * 2 <= cnt && h[u * 2] < h[t]) t = 2 * u;
	//右儿子
	if (u * 2 + 1 <= cnt && 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];
	cnt = n;
	//从第一个非叶节点开始，从右到左，从下到上处理每个节点(即初始化堆)
	for (int i = n / 2; i >= 1; i--) down(i);
	while(m--)
	{
		cout << h[1] << " ";
		h[1] = h[cnt--];
		down(1);
	}
	
	
	
	return 0;
}