堆

不是STL里面的堆，而是手写堆。

堆最基本的操作：

1. 堆集合中插入一个数
2. 求集合中的最小值
3. 删除集合中的最小值

STL堆只支持这3个操作

4. 删除任意一个元素
5. 修改任意一个元素

这两个操作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算法中会用到，其他不常用