堆-- 神奇的优先队列

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

有没有发现这棵二叉树有一个特点？就是所有的父节点都比子节点小（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 ;
}