模拟堆

模拟堆概述

模拟堆相对于基础的堆，增加了修改和删除任意元素的功能

而这个功能也是建立在指针索引的基础上才能实现的，所以我们开辟了$hp$[ ]与$ph$[ ]两个数组的基础上(起指针作用)

$hp$[ ] 可以看做是$heap$ $pointer$或者 $heap$ $to$ $position$简写，即堆中元素到第$k$个插入元素的映射

$ph$[ ] 可以看做是$pointer$ $heap$或者 $position$ $to$ $heap$简写，即第$k$个插入元素到堆中元素的映射

组成

$h[N]$存储堆中的值, $h[1]$是堆顶，$x$的左儿子是$2x$, 右儿子是$2x + 1$

$ph[k]$存储第$k$个插入的点在堆中的位置

$hp[k]$存储堆中下标是k的点是第几个插入的

$size$是维护的堆的大小，$m$是插入的次数
$m$最好是作为全局变量在上面声明，它们是一套体系

不过y总是在底下声明的

    int h[N], ph[N], hp[N], size, m;

堆中的交换

模拟堆需要维护两个映射的关系，所以交换堆中元素时候，不能简单的使用$swap$，因为交换元素后，两组指针的指向都会错位

所以在交换时候，除去元素的交换外，指针指向（映射关系）也是我们要维护的内容

交换时候，可以想想画的两根互相指着的线，就像上面的图

先交换两侧指针指向，最后交换元素

首先有通过$hp$[ ]数组，得到堆中元素对应的是第$k$个插入数，交换$ph$[ ]数组
交换由堆像插入的映射数组
交换元素

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

其余操作

其余操作和普通堆一样，只是在涉及交换的时候一律采勇堆交换，因为需要维护映射关系

代码

#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

const int N = 100010;

int h[N], ph[N], hp[N], cnt;

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 <= 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)
    {
        heap_swap(u, t); // 均采用堆交换
        down(t);
    }
}

void up(int u) // 上滤操作
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2); // 采用堆交换
        u >>= 1;
    }
}

int main()
{
    int n, m = 0;
    scanf("%d", &n);
    while (n -- )
    {
        char op[5];
        int k, x;
        scanf("%s", op);
        if (!strcmp(op, "I")) //插入操作
        {
            scanf("%d", &x);
            cnt ++ ; // 堆的大小加一
            m ++ ; //插入加一
            ph[m] = cnt, hp[cnt] = m; //维护映射关系
            h[cnt] = x; //堆中元素赋值
            up(cnt); //是在末位加入的，上滤即可
        }
        else if (!strcmp(op, "PM")) printf("%d\n", h[1]);
        else if (!strcmp(op, "DM")) //删除最小值
        {
            heap_swap(1, cnt);
            cnt -- ;
            down(1);
        }
        else if (!strcmp(op, "D")) //删除任意值
        {
            scanf("%d", &k);
            k = ph[k]; // 通过ph[ ]数组由k索引到它在堆中的下标，然后进行操作
            heap_swap(k, cnt); //将最后一个元素覆盖当前元素
            cnt -- ;
            up(k); // 交换完，可能会变大、也可能变小，down和up各一遍，两个操作只有一个会支持
            down(k);
        }
        else
        {
            scanf("%d%d", &k, &x);
            k = ph[k];
            h[k] = x; // 修改任意元素
            up(k);
            down(k);
        }
    }

    return 0;
}