堆
不是STL里面的堆，而是手写堆。
堆最基本的操作：
- 堆集合中插入一个数
- 求集合中的最小值
- 删除集合中的最小值
STL堆只支持这3个操作
- 删除任意一个元素
- 修改任意一个元素
这两个操作STL中堆无法实现。STL堆是优先队列实现的,不是二叉树
堆是一个完全二叉树（上层节点是满的，最后一层节点从左向右排列）。
堆的实现使用一个数组，但是这个数组存储的时候以一种特殊的方式排列。节点x的左儿子2x，右儿子2x+1。（完全二叉树都是这样存储），这也造就了堆。
==一维数组可以存储一个完全二叉树（堆），就是这么神奇！！==
// 基础操作 heapify
void down(int i){ //输入的是节点的编号，不是节点的值 节点的值是h[i]
/*
down的目的是 形成局部小三角到合适的位置
*/
int u = i; // 先假定当前节点是最小值 ,u和i是节点编号不是节点的值
if(2*u <= size && h[2*u] <h[i]) u = 2*i;
if(2*u+1 <= size && h[2*u+1] < h[i]) u = 2*i+1;
if(u != i) //如果u和最初的i不相等
{
swap(h[u],h[i]);
down(u);
}
}
void up(){
// up则用到了迭代,也能递归写法.迭代和递归一定可以相互转化
while(u/2 && h[u/2] > h[u]){
swap(h[u/2],h[u]);
u = u/2;
}
}
// down操作和up操作可以形成堆的5个基本功能
image-20220228162533101
注意堆的使用需要下标从1开始
// 堆排序
#include <iostream>
using namespace std;
const int N = 10e5+10;
int h[N],siz; // size记录堆数组中目前一共放了多少个数
int n,m;
void down(int i){
int u = i;
if(2 * i <=siz && h[2*i] < h[u]) u = 2*i;
if(2 * i + 1 <= siz && h[2*i+1] < h[u]) u = 2*i+ 1;
if(u != i){
swap(h[u],h[i]);
down(u);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i<=n;i++) cin >> h[i]; // 先放入数组
siz = n;
for(int i = n/2;i>=1;i--){ // 建堆（调整数组元素的放置） 这个题建堆可以一个一个往里面插入但是这样的时间复杂度是O(nlogn)
// 从n/2开始down一遍建堆时间复杂度是O(n)
down(i); // 从倒数第二层到根节点不断的down下面的两个节点
}
while(m--){
// 1.输出最小值
cout << h[1] << " ";
// 2. 删除根
h[1] = h[siz];
siz--;
down(1); // down本身是个递归函数 从根顶开始down可以扩散到所有元素
}
return 0;
}
进阶版
还有一种带映射版的复杂的堆。这种堆在Dijsktra算法中会用到，其他不常用
