[编程笔记]-Heap堆

实质

事实上，堆就是一棵完全二叉树。

在堆中，以小根堆为例，每个父节点总是小于等于子节点的。

所以根节点事实上就是最小值。

作用

1. 插入一个数
2. 求集合当中的最小值
3. 删除最小值
4. 删除任意元素（STL做不到）
5. 修改任意元素（STL做不到）

实现

存储

利用一维数组实现，2x是x左子节点，2x+1是x右子节点。

基操

根有两个基本操作：上移和下移，就是把节点与父节点/子节点互换以维护堆的单调性。

初始化

先随便把元素存进去，然后对前n/2个元素从后往前进行下移操作，就能完成初始化操作。

时间复杂度

O(n)。但这个证明有点复杂，就不在这里放出了。

插入

随便新建一个叶节点，然后执行上移操作。

求最小值

根节点啊。

删除最小值

将根节点和最后一个节点互换一下，然后直接删掉尾节点（原根节点），最后下移操作维护。

y总的奇妙比喻：现在有一队人，直接杀队头肯定不方便，那么把队头队尾狸猫换太子，直接K掉队尾，神不知鬼不觉，最后维持下秩序就OK了Σ(っ °Д °;)っ

删除任意元素

和删除最小值一样，不过最后上移下移都要试一遍。

修改任意元素

同理，修改指定元素后，上移一遍下移一遍欸，好了（￣︶￣）

堆排序

啊这个堆排序的话只需要获取最小值&输出最小值就OK了，所以其实只会用到下移操作，所以您也跟我一样够懒的话只写下移函数就可以了。

时间复杂度

毕竟是树嘛，所以很快得出是O(logn)啦。

代码

堆排序

还是给一道板子题吧：
AcWing838-堆排序

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;

int n,m;
int a[N];

void down(int now){
    int son=now;
    if(now*2<=n&&a[now*2]<=a[son])son=now*2;
    if(now*2+1<=n&&a[now*2+1]<=a[son])son=now*2+1;
    if(now!=son){
        swap(a[now],a[son]);
        down(son);
    }
}

void heap_sort(){
    for(int i=n/2;i>=1;i--){
        down(i);
    }
}

int main(){
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    heap_sort();
    for(int i=1;i<=m;i++){
        cout<<a[1]<<" ";
        swap(a[1],a[n--]);
        down(1);
    }
    return 0;
}

模拟堆

注意，这个堆中还记录了插入结点的编号，所以在细节上硬控我半小时(ノへ￣、)

class heap{
    public:
        int idk,n;
        int h[N],ph[N],hp[N];//ph是编号对应的下标，hp是下标对应的编号。
        void heap_swap(int a,int b){
            swap(h[a],h[b]);
            swap(ph[hp[a]],ph[hp[b]]);
            swap(hp[a],hp[b]);
        }
        void up(int x){
            while(x>1){
                if(h[x/2]<=h[x])break;
                heap_swap(x/2,x);
                x/=2;
            }
        }
        void down(int x){
            while(x<=n){
                int t=x;
                if(x*2<=n&&h[x*2]<h[t])t=x*2;
                if(x*2+1<=n&&h[x*2+1]<h[t])t=x*2+1;
                if(t==x)break;
                heap_swap(x,t);
                x=t;
            }
        }
        void insert(int x){
            h[++n]=x;
            ph[++idk]=n;
            hp[n]=idk;
            up(n);
        }
        int getmin(){
            return h[1];
        }
        void delmin(){
            heap_swap(1,n--);
            down(1);
        }
        void delid(int k){
            int ok=ph[k];
            heap_swap(ph[k],n--);
            down(ok);
            up(ok);
        }
        void changeid(int k,int x){
            h[ph[k]]=x;
            down(ph[k]);
            up(ph[k]);
        }
}hp;

完结撒花o(￣︶￣)o