堆是一个完全二叉树，使用顺序存储结构。

(1是根节点，i的左孩子结点的下标为2*i，右孩子结点的下标为2*i+1)。

大根堆：每个结点的值都比左子树和右子树所有结点的值大。

小根堆：每个结点的值都比左子树和右子树所有结点的值小。

排序思想
1.将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是堆结构的顶端

2.将顶端的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组个数为n-1(进行删除根节点操作)

3.将剩余的n-1个数再构造成大根堆(只需进行一次down操作)，再将顶端数与n-1位置的数交换，如此反复执行，便能得到有序数组。

堆的基本操作：调整：up(x); down(x)；

（1）插入一个数：heap[++size]=x;up(size)；

把这个数放到完全二叉树的最后，然后对这个数进行up调整。

（2）求集合当中的最小值：heap[1]；

（3）删除最小值：heap[1]=heap[size];size--;down(1);

用完全二叉树的最后一个数替换根节点，然后对根节点进行down调整。

（4）修改任意一个元素：heap[k]=x；down(k)；up(k)；

修改对应元素后，先进行down操作，再进行up操作。

down(x)操作(小根堆为例)：(log(n))

比较x与其左右孩子结点的大小关系，如果比左右孩子大，就交换两个结点。

void down(int u){
   int t=u;
   if(u * 2<=size && h[u*2]<h[t]) t = u*2;
   if(u * 2<=size && h[u*2+1]<h[t]) t = u*2+1;
   // t表示u和左孩子和右孩子最小值的下标
   // 如果u不是最小的,就交换x和t，并且递归对tdown操作
   if(u!=t){
      swap(h[u],h[t]);
      down(t);
   }
}