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

这篇具有很好参考价值的文章主要介绍了【第十五课】数据结构：堆(acwing-839模拟堆 / ph和hp数组的映射关系 /c++代码 )。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

注意点

代码如下

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

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

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

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

注意点

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

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

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

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

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

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

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

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

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

代码如下

#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;
}

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

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

有问题欢迎指出！一起加油！！文章来源地址https://www.toymoban.com/news/detail-824676.html

到了这里，关于【第十五课】数据结构：堆(acwing-839模拟堆 / ph和hp数组的映射关系 /c++代码 )的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！