堆

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

堆最基本的操作：

1. 堆集合中插入一個數(shù)
2. 求集合中的最小值
3. 刪除集合中的最小值

STL堆只支持這3個操作

4. 刪除任意一個元素
5. 修改任意一個元素

這兩個操作STL中堆無法實現(xiàn)。STL堆是優(yōu)先隊列實現(xiàn)的,不是二叉樹

堆是一個完全二叉樹（上層節(jié)點是滿的，最后一層節(jié)點從左向右排列）。

堆的實現(xiàn)使用一個數(shù)組，但是這個數(shù)組存儲的時候以一種特殊的方式排列。節(jié)點x的左兒子2x，右兒子2x+1。（完全二叉樹都是這樣存儲），這也造就了堆。

==一維數(shù)組可以存儲一個完全二叉樹（堆），就是這么神奇！！==

// 基礎(chǔ)操作 heapify
void down(int i){  //輸入的是節(jié)點的編號，不是節(jié)點的值 節(jié)點的值是h[i]
  /*
  down的目的是 形成局部小三角到合適的位置
  */
  
  int u = i; // 先假定當前節(jié)點是最小值 ,u和i是節(jié)點編號不是節(jié)點的值
  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則用到了迭代,也能遞歸寫法.迭代和遞歸一定可以相互轉(zhuǎn)化
  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記錄堆數(shù)組中目前一共放了多少個數(shù)
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];  // 先放入數(shù)組
    siz = n;
    for(int i = n/2;i>=1;i--){     // 建堆（調(diào)整數(shù)組元素的放置） 這個題建堆可以一個一個往里面插入但是這樣的時間復(fù)雜度是O(nlogn) 
                                   // 從n/2開始down一遍建堆時間復(fù)雜度是O(n)
        
        down(i);                   // 從倒數(shù)第二層到根節(jié)點不斷的down下面的兩個節(jié)點
        
    }
    
    
    while(m--){
        // 1.輸出最小值
        cout << h[1] << " ";
        // 2. 刪除根
        h[1] = h[siz];
        siz--;
        down(1); // down本身是個遞歸函數(shù) 從根頂開始down可以擴散到所有元素
        
    }  
    return 0;
}

進階版

還有一種帶映射版的復(fù)雜的堆。這種堆在Dijsktra算法中會用到，其他不常用