2.3 堆

如何手写一个堆，功能

把整个数组建成堆，每次把堆顶输出出来，第一次堆顶就是第一小的数，第二次就是第二小的数…

• 插入一个数

heap[++ size] = x; up(size);//在堆的最后一个位置加上一个数，不断往上移

• 求集合中的最小值

heap[1];//根节点是最小的

• 删除最小值

heap[1] = heap[size];size --; down(1);
// 用最后一个点覆盖第一个点，把最后一个点删掉，让1号点往下走

• 删除任意一个元素

heap[k] = heap[size]; size --; down(k); up(k);
// up,down只会执行一个

• 修改任意一个元素

heap[k] = x; down(k); up(k);

堆的基本结构（以小根堆为例）

• 完全二叉树（叶子节点只会出现在最后2层，且最后一层的叶子节点都靠左对齐。）

性质

• 每个节点的值小于等于两个子节点
• 根节点就是最小值

堆的存储

• 用一维数组来存，1号点是根节点
• x的左儿子：2 x， x的右儿子， 2 x + 1（所以下标从1开始更方便）

堆的两个基本操作

• down(x) 往下调整（把节点往下移）， 把某一个值变大了，因为是小根堆，就要把这个值往下压。每次找找该节点和其子节点的最小值，找到了就和这个交换。
• up(x) 往上调整（把节点往上移），把一个数变小了，就要往上。每次只要跟它的父节点比较，如果比父节点小了就和根节点交换（往上移）。

void up(int u){
    while(u / 2 && h[u / 2] > h[u]){
        swap(h[u / 2], h[u]);
        u = u / 2;
    }
}

void down(int u){
    int t = u;//t表示三个点中的最小值

    //使t存最小的那个点的编号
    if(u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if(u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if(u != t){//根节点不是最小值的话
        swap(h[u], h[t]);
        down(t);
    }
}

堆排序代码

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;
int h[N];
int n, m, cnt;

void down(int u){
    int t = u;//t表示三个点中的最小值

    //使t存最小的那个点的编号
    if(u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if(u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if(u != t){//根节点不是最小值的话
        swap(h[u], h[t]);
        down(t);
    }
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
    cnt = n;

    for(int i = n / 2; i; i --) down(i);//时间复杂度o(n),如果一个一个插入是nlog(n)

    while(m --){
        printf("%d ", h[1]);
        h[1] = h[cnt];
        cnt --;
        down(1);
    }
}

模拟堆代码

#include<iostream>
#include<cstring>
using namespace std;

const int N = 100010;
int h[N], hp[N], ph[N], Size;

// ph[i]保存的是第i个插入的数的数组下标，hp[i]保存的是数组下标为i的数是第几个插入的
void heap_swap(int a, int b){ 
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u){
    int t = u;
    if(u * 2 <= Size && h[u * 2] < h[t]) t = u * 2;
    if(u * 2 + 1 <= Size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if(u != t){
        heap_swap(u, t);
        down(t);
    }
}

void up(int u){
    while(u / 2 && h[u / 2] > h[u]){
        heap_swap(u / 2, u);
        u /= 2;
    }
}

int main(){
    int n;
    scanf("%d", &n);
    int m = 0;
    while(n --){
        char op[5];
        int k, x;
        scanf("%s", op);
        if(!strcmp(op, "I")){
            scanf("%d", &x);
            Size ++;
            m ++;
            ph[m] = Size;
            hp[Size] = m;
            h[Size] = x;
            up(Size);
        }
        else if(!strcmp(op, "DM")){
            heap_swap(1, Size);
            Size --;
            down(1);
        }
        else if(!strcmp(op, "PM")){
            printf("%d\n", h[1]);
        }
        else if(!strcmp(op, "D")){
            scanf("%d", &k);
            k = ph[k];//获得第k个插入数的数组下标
            heap_swap(k, Size);
            Size --;
            down(k), up(k);
        }
        else{
            scanf("%d%d", &k, &x);
            k = ph[k];
            h[k] = x;
            down(k), up(k);
        }
    }

    return 0;
}