堆————神奇的优先队列

堆——神奇的优先队列

//建堆以及堆排序
#include<iostream>
using namespace std;
int h[101];//存放堆的数组
int n;//用来存储堆中元素的个数，也就是堆的大小

void swap(int x, int y) {
	int t;
	t = h[x];
	h[x] = h[y];
	h[y] = t;
	return;
}

//向下调整函数
void siftdown(int i)//从1开始，向下调整
{
	int t, flag = 0;//flag用来标记是否需要继续向下调整
	//当i节点有儿子的时候才向下执行
	while (i * 2 <= n && flag == 0) {
		//首先判断它与左儿子的关系，用t记录值比较小的节点的编号
		if (h[i] > h[i * 2])
			t = i * 2;
		else
			t = i;
		//再判断它与右儿子的关系，用t记录值比较小的节点的编号
		if (i * 2 + 1 <= n) {
			//如果右儿子更小，更新较小的节点编号
			if (h[t] > h[i * 2+1]  )
				t = i * 2 + 1;
		}
		//如法发现最小的节点编号不是自己，说明有比父节点更小的
		if (t != i) {
			swap(i, t);//交换值
			i = t;//更新i为刚才与它交换的儿子节点的编号，便于继续进行调整
		}
		else
			flag = 1;
	}
	return;
}

//这是用堆排序的方法所用到的调整函数，目的在于建立最大堆
void siftdown1(int i) {
	int t, flag = 0;
	while (i * 2 <= n && flag == 0) {
		if (h[i] < h[i * 2])
			t = i * 2;
		else
			t = i;
		if (i * 2 + 1 <= n) {
			if (h[t] < h[i * 2 + 1])
				t = i * 2 + 1;
		}
		if (t != i) {
			swap(i, t);
			i = t;
		}
		else
			flag = 1;
	}
	return;
}

//堆排序
void heapsort() {
	while (n > 1) {
		swap(1, n);
		n--;
		siftdown1(1);
	}
}

//建立堆的函数
//从最后一个非叶节点到第一个节点依次进行向下调整
void create() {
	int i;
	for (i = n / 2; i >= 1; i--)
		siftdown(i);
	return;
}
//堆排序方法的建立最大堆
void creat() {
	int i;
	for (i = n / 2; i >= 1; i--)
		siftdown1(i);
	return;
}
//删除最大的元素
int deletemax()
{
	int t;
	t = h[1];//临时变量记录定点值
	h[1] = h[n];//将堆的最后一个点赋值到堆顶
	n--;//堆的元素个数减少一
	siftdown(1);//向下调整
	return t;//返回之前记录的定点最小值
}

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


	create();//建堆

	//连续删除n次顶部元素，也就是从小到大把数输出来
	for (i = 1; i <= num; i++)
		printf("%d ", deletemax());
	

	scanf("%d", &num);
	for (i = 1; i <= num; i++)
		scanf("%d", &h[i]);
	n = num;
	creat();
	heapsort();//堆排序
	for (i = 1; i <= num; i++)
		printf("%d ", h[i]);
	getchar();
	getchar();
}

运行结果如下：

咳咳，运行结果被我搞没了，总而言之是按照升序排列就对了。

最后贴上我的良师益友的照片来镇楼。