堆-- 神奇的优先队列

堆是什么？是一种特殊的完全二叉树，就像树一样。

有没有发现这棵二叉树有一个特点？就是所有的父节点都比子节点小（PS ：就是圆圈的数值，圆圈外面的编号是这个节点的编号，）那么符合这样特点的我们称之为最小堆。

#include <iostream>
#include <cstdio>
using namespace std ;
const int MAX = 1000 ;
const int INF = 0x3f3f3f3f ;


int n , m ;
// 堆 -- 神奇的优先队列;
int h[MAX];
// 交换函数，用来交换堆中两个元素的值;
void swap(int x ,int y)
{
	int t ;
	t = h[x] ;
	h[x] = h[y] ;
	h[y] = t ;
	return ;
}
// 向下调整函数;
void siftdown(int i)
{
	int t ,flag =0 ; // flag 用来标记是否需要向下调整
	// 当i有子节点的时候，并且需要调整的时候循环就执行;
	
	while( i*2 <=n && flag==0)
	{
		// 首先判断i即父节点与左儿子的关系,并用t来记录值较小的结点编号
		
		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(t,i);
			i =t ; // 更新i为刚才与他交换的儿子节点的编号,便于接下来继续向下调整

		}
		else
			flag = 1 ; // 说明父节点的值比 子节点的值都要小 ;
			

	}
	return ;
}
// 建立堆函数;
void creat()
{
	int i ;
	for(i=n/2 ;i>=1 ;i--)
	{
		siftdown(i) ;
	}
	return ;
	
}
// 删除最大元素;
int deletemax()
{
	int t ;
	t = h[1] ; // 用一个临时变量t 来记录堆顶的值;
	h[1] =h[n] ; // 将堆的最后一个点复制到堆顶
	n-- ;// 对的元素减少;
	siftdown(1);
	return t ;

}
int main()
{
	
	int i , num ;
	cin >>num ;
	for(i=1;i<=num ;i++)
	{
		cin>>h[i] ;
	}
	n = num ;
	creat();
	for(i=1;i<=num ;i++)
	{
		printf("%d ",deletemax());
	}

	return 0 ;
}