堆

堆是一颗完全二叉树,除了最底层之外其他层结点都是满的.这里我们取小根堆,有如下性质:

1.若k为某结点编号,其父结点编号为k/2,左子节点2k,右子节点2k+1

2.堆结点A若有子节点,则A的值小于(两个)子节点的值(若是大根堆就变成大于),两个子节点的值的大小不管

3.堆顶一定为堆中最小值(性质2的推论)

4.堆底层存满时时第二层元素为n/4个

堆的存储:

int heap[N], idx;

由于堆是一颗完全二叉树故可正好占满一个序列的位置,所以用数组存,idx代表用到点的个数.一般点要从1开始用(后文解释).

堆的一般操作:

1.down

down(t)代表把t元素下移,希望把t移到符合堆性质的位置.具体实现是比较t元素与其子节点值的大小(如果存在),假设存在a,b子节点,若t值小于a大于b则与t与a交换,若t值小于a小于b且b比a小则与b交换,这样逐渐向下直到字节点a’,b’的值都大于t为止.

t的值是堆中元素的下标.

void down(int k) {
    int t = k;
    if (2 * k <= idx && heap[2 * k] < heap[t]) t = 2 * k; //注意这里如果点从0开始用2*0还是0,不方便
    //!注意这里是heap[2 * k] < heap[t] 如果写成heap[2 * k] < heap[k] 就只跟k节点比大小了,没跟两个子节点没比大小
    if (2 * k + 1 <= idx && heap[2 * k + 1] < heap[t]) t = 2 * k + 1;
    if (t != k) {//t值不等于k值时,意味着可以交换/下移
        swap(heap[t], heap[k]);
        down(t);//由于是一颗完全二叉树,1e9的元素也不过三十层,所以直接递归
    }
}

2.up

up(t)代表把t元素上移,希望把t移到符合堆性质的位置.与down类似但相反,具体实现是比较t元素与其父节点值的大小(如果存在),若大于父节点值则交换,直到父节点值小于t/不存在父节点为止.

t的值是堆中元素的下标.

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

3.建堆

建堆之前肯定是要输入元素的.注意点从1开始标号.

有一种O(n)的建堆方法:从所给数据的中点n/2开始向前遍历,遍历一个元素t就down(t).为什么是正确的?因为若从1开始标号,n/2正好是第二层结点,n/2元素右侧如果有结点是不需要down的,因为他们没有子结点而且是底层;又由于最后一层结点大小不管,只需要down包括n/2及前面的元素(可以手画一下),第二层元素(期望n/4个)最多down一次,第三层最多down两次,每层结点都是子节点数的1/2,有

$$\frac{\mathrm{n}}{4}+2\cdot \frac{\mathrm{n}}{8}+3\cdot \frac{\mathrm{n}}{16}+\cdot \cdot \cdot +\left( \mathrm{n}-1 \right) \frac{\mathrm{n}}{2^{n+1}}\sim \mathrm{O}\left( \mathrm{n} \right) $$

for (int i = n / 2; i; i--) {
    down(i);
}

4.堆顶删除

先让堆顶heap[1] = heap[idx]堆尾,那么堆顶值就被删了,然后堆中此时有两个值为heap[idx]的元素,此时令idx–,那么堆尾元素就被删了,剩下原来堆顶元素的位置的值等于原堆尾,此时down(heap[1])即可.弹出堆顶等价于输出最小值,所以也相当于排序.

heap[1] = heap[idx];
idx--;
down(1);//down(t),t的值是堆中元素的下标.

堆的进阶版

先看例题,按例题分析

https://www.acwing.com/problem/content/242/
维护一个集合，初始时集合为空，支持如下几种操作：
I x，插入一个数 x；
PM，输出当前集合中的最小值；
DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
D k，删除第 k 个插入的数；
C k x，修改第 k 个插入的数，将其变为 x；
现在要进行 N 次操作，对于所有第 2 个操作，输出当前集合的最小值。
输入格式
第一行包含整数 N。
接下来 N 行，每行包含一个操作指令，操作指令为 I x，PM，DM，D k 或 C k x 中的一种。
输出格式
对于每个输出指令 PM，输出一个结果，表示当前集合中的最小值。
每个结果占一行。
数据范围
1≤N≤105
−109≤x≤109
数据保证合法。
输入样例：
8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM
输出样例：
-10
6
//题目要求任意位置删除,修改.

1.存储

进阶版的堆支持修改删除任意元素(这里指按输入顺序的任意第k个点).为了能够达到这个条件,需要保存输入时堆中元素的位置,也能够根据堆中元素位置找到插入的顺序.

int heap[N];  //堆
int ph[N];    //存放第k个插入点的在堆中的下标
int hp[N];    //存放堆中i点的插入次序
int idx;      // idx 记录的是堆当前的数据多少

用了两个表达意义互为反函数的两个数组ph和hp

2.swap函数

由于up和down操作需要交换元素,那么对应点的ph和hp值也需要交换,因此要升级swap函数,同样的在up\down函数中的swap要变成升级后的swap函数.

void heap_swap(int a, int b) {
    swap(heap[a], heap[b]);
    swap(hp[a], hp[b]);
    swap(ph[hp[a]], ph[hp[b]]);
}

这里a,b为堆中下标,令k1,k2为a,b的插入次序,则k1=hp[a],k2=hp[b],交换堆中的值就是swap(heap[a],heap[b]),两个点相互交换那么一开始插入的顺序也要交换,即为swap(hp[a],hp[b]),按插入顺序的第k1,k2个点在堆中的下标也要交换,即swap(ph[k1],ph[k2])~swap(ph[hp[a]],ph[hp[b]]).这三条语句的顺序可以变,因为相对独立.

3.堆顶删除

heap_swap(1, idx);
idx--;
down(1);//没变化,和普通堆一样

4.插入堆尾操作

插入的时候按照上文就要记录插入的数的次序m,也是总共插入的数.(和idx不一样,idx是数据个数,删除了元素就比m小)

由于插入的时堆尾只需要up即可.m要++,要先更新ph,hp再up,因为一旦up里面就要交换,但交换的时候找不到ph[m]和hp[idx],所以要先更新ph,hp再up(idx).

scanf("%d", &x);
m++;
heap[++idx] = x;//堆尾
ph[m] = idx;
hp[idx] = m;
up(idx);

5.删除插入的第k个元素

删除插入顺序的第k个点与堆顶删除类似,让heap[ph[k]] = heap[idx]对吗? 不对,因为删除元素要更新ph和hp,所以用堆交换heap_swap(ph[k],idx), 令idx–,那么堆尾元素就被删了,然后down(?) down什么呢?down接收堆中元素的下标也就是ph[k],而这里ph[k]是交换后k点在堆中元素的下标,因为ph[k]在上一句heap_swap的时候已经被更改了,所以要用临时变量保存ph[k]

由于元素要么down要么up 干脆都执行(要意识到堆尾不一定是最大值,最大值存在于最后一层,如果删除的元素所在的子树的元素都很大,那么原堆尾是有可能up然后去另外一颗子树)

scanf("%d", &k);
int u = ph[k];  //这里一定要用u=ph[k]保存第k个插入点的下标
heap_swap(u, idx);  //因为在此处heap_swap操作后ph[k]的值已经发生
idx--;  //如果在up,down操作中仍然使用ph[k]作为参数就会发生错误
down(u);
up(u);

6.修改插入的第k个元素

直接修改值然后down,up就行.

scanf("%d%d", &k, &x);
heap[ph[k]] =
x;  //此处由于未涉及heap_swap操作且下面的up、down操作只会发生一个所以
up(ph[k]);
down(ph[k]);  //所以可直接传入ph[k]作为参数

代码:

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

const int N = 1e5 + 10;
int heap[N];  //堆
int ph[N];    //存放第k个插入点的下标
int hp[N];    //存放堆中点的插入次序
int idx;      // size 记录的是堆当前的数据多少

//这个交换过程其实有那么些绕 但关键是理解 如果hp[u]=k 则ph[k]=u 的映射关系
//之所以要进行这样的操作是因为 经过一系列操作 堆中的元素并不会保持原有的插入顺序
//从而我们需要对应到原先第K个堆中元素
//如果理解这个原理 那么就能明白其实三步交换的顺序是可以互换
// h,hp,ph之间两两存在映射关系 所以交换顺序的不同对结果并不会产生影响
void heap_swap(int a, int b) {
    swap(heap[a], heap[b]);
    swap(hp[a], hp[b]);
    swap(ph[hp[a]], ph[hp[b]]);
}
void down(int u) {
    int t = u;
    if (u * 2 <= idx && heap[t] > heap[u * 2]) t = u * 2;
    if (u * 2 + 1 <= idx && heap[t] > heap[u * 2 + 1]) t = u * 2 + 1;
    if (u != t) {
        heap_swap(u, t);
        down(t);
    }
}
void up(int u) {
    if (u / 2 > 0 && heap[u] < heap[u / 2]) {
        heap_swap(u, u / 2);  //!不能写heap[u] heap[u/2]
        up(u >> 1);
    }
}
int main() {
    int n;
    cin >> n;

    int m = 0;  // !! 一定记得初始化本地变量!!!!
    //      m用来记录插入的数的个数
    //注意m的意义与idx是不同的 idx是记录堆中当前数据的多少
    //对应上文 m即是hp中应该存的值
    while (n--) {
        char op[5];
        int k, x;
        cin >> op;
        if (op[0] == 'I') {
            scanf("%d", &x);
            m++;
            heap[++idx] = x;
            ph[m] = idx;
            hp[idx] = m;
            up(idx);
        } else if (op[0] == 'P')
            printf("%d\n", heap[1]);
        else if (op[0] == 'D' && op[1] == 'M') {
            heap_swap(1, idx);
            idx--;
            down(1);
        } else if (op[0] == 'D') {
            scanf("%d", &k);
            int u = ph[k];  //这里一定要用u=ph[k]保存第k个插入点的下标
            heap_swap(u, idx);  //因为在此处heap_swap操作后ph[k]的值已经发生
            idx--;  //如果在up,down操作中仍然使用ph[k]作为参数就会发生错误
            down(u);
            up(u);

        } else {
            scanf("%d%d", &k, &x);
            heap[ph[k]] =
                x;  //此处由于未涉及heap_swap操作且下面的up、down操作只会发生一个所以
            up(ph[k]);
            down(ph[k]);  //所以可直接传入ph[k]作为参数
        }
    }
    return 0;
}