【第十五课】数据结构：堆(acwing-839模拟堆 / ph和hp数组的映射关系 /c++代码 )

目录

注意点?

代码如下?

---

上篇已经详细解释过堆的内容，需要可以回顾一下。

【第十五课】数据结构：堆

这里关注这道题提出几个注意点。?

注意点?

这道题有几个需要注意的点：

①没有事先给出完整的数组，而是靠我们一次次操作进行插入。因此，要定义一个size变量记录插入数据的个数

②对于操作4 5 .要求是删除/修改 “第k个插入的数”。 //这是这道题的重点

由于堆是一种动态变化的数据结构，元素在堆中的位置会随着插入和删除操作的进行而发生改变，所以我们不能简单地将插入的顺序和在堆中的位置直接对应起来，需要通过ph和hp两个数组来进行转换。

因此，我们在交换堆数组中两个数据的时候不能单单只是交换其在数组中的值，还需要更新ph和hp两个数组，以保持元素的? 位置信息和插入顺序? 的信息始终是正确的(映射关系)

需要着重理解ph和hp两个数组所代表的含义。

ph数组用来记录第k个插入的数在堆数组中的下标，也就是：ph数组的下标，表示的是第几个插入，ph数组的含义是 第k个插入的数在堆数组中的下标。

hp数组用来记录堆数组中的每个元素对应是第几个插入的，也就是：hp数组的下标，表示的是堆数组中元素的下标，hp数组的含义是堆数组中的每个元素对应是第几个插入的。

代码如下?

#include<iostream>
#include<algorithm>
const int N=1e5+10;
int n,size;
int he[N],ph[N],hp[N];
//size 记录元素个数
//ph数组：存储第k个插入的数 在堆数组中的下标  hp数组：存储 堆里面对应下标的点是 第几个插入的点
using namespace std;

void heap_swap(int a,int b)//a b表示下标 注意传入变量的形式
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a],hp[b]);
    swap(he[a],he[b]);
}
void down(int x)
{
    int t=x;//t表示三个数中的最小值
    if(x*2<=size && he[x*2]<he[t])t=x*2;
    if(x*2+1<=size && he[x*2+1]<he[t])t=x*2+1;
    if(x!=t)
    {
        heap_swap(x,t);
        down(t);
    }
}
void up(int x)
{
    while(x/2 && he[x/2]>he[x])
    {
        heap_swap(x/2,x);
        x /= 2;
    }
}
int main()
{
    scanf("%d",&n);
    while(n--)
    {
        char op[2]={0};
        scanf("%s",op);
        int k,x;
        int i=0;//i被用作ph数组的索引
        if(op[0]=='I')
        {
            scanf("%d",&x);
            size++;
            i++;
            ph[i]=size;
            hp[size]=i;
            he[size]=x;
            up(size);
        }
        else if(op[0]=='P')
        {
            printf("%d\n",he[1]);
        }
        else if(op[0]=='D' && op[1]=='M')
        {
            heap_swap(1,size);
            size--;
            down(1);
        }
        else if(op[0]=='D' && op[1]!='M')
        {
            scanf("%d",&k);
            k=ph[k];
            heap_swap(k,size);
            size--;
            down(k);
            up(k);
        }
        else {
            scanf("%d%d",&k,&x);
            k=ph[k];
            heap_swap(k,size);
            he[k]=x;
            down(k);
            up(k);
        }
    }
    return 0;
}

在明白上篇文章和注意点之后，相信代码很容易理解。

---

关于堆的问题就先说到这里。

有问题欢迎指出！一起加油！！?