[C++知识库]简单堆排序

以小根堆为例
//插入结点x? ? ? ? 
heap[++large] = x; up(large);
//最小结点
return heap[1];
//删除最小结点
heap[1] = heap[large--]; down(1);
//删除编号k的结点
heap[k] = heap[large--]; down(k); up(k);
//修改编号k的结点x
heap[k] = x; down(k); up(k);

???????

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int heap[N]； //小根堆
int large;    //堆大小
void down(int k)    //若k结点变大了，则做下降调整
{
	int t = k;
	if (2 * k <= large&&heap[2 * k]<heap[t])t = 2 * k;
	if (2 * k + 1 <= large&&heap[2 * k + 1]<heap[t])t = 2 * k + 1;
	if (t != k)
	{
		int temp = heap[t]; heap[t] = heap[k]; heap[k] = temp;
		down(t);
	}
}
void up(int k)    //若k结点变小了，则做上升调整
{
	int t = k;
	if (k / 2 && heap[k / 2]>heap[t])t = k / 2;
	if (t != k)
	{
		int temp = heap[k]; heap[k] = heap[t]; heap[t] = temp;
		up(t);
	}
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &heap[i]);
	}
//o(n)由数组建堆
	large = n;
	for (int i = n / 2; i; i--)down(i);
    /*
//o(nlogn)建堆 比较慢
    large=0;
    for(int i=1;i<=n;i++)
    {
        up(++large);
    }
    */
	while (m--)
	{
		printf("%d ", heap[1]);
		heap[1] = heap[large];
		large--;
		down(1);
	}
	return 0;
}