模拟堆
题目 模拟堆
思路分析
其实考虑的就是 如果要对第k个元素进行操作的话
先前的那种只换值的方式就不够了
要使得这些数在交换位置后仍不失物理上的有序性 就还得一个东西去维护这个关系
我的想法是类似于用模拟链表的方式
用一个数组专门去存值
而这个堆数组存放的是这个值对应的在数组1中的下标
然后两者间还是用下标去对应
而这里给出的方法是 原本逻辑不改变 额外开两个数组
ph（point->heap）可以获得第几个插入的元素现在在堆的那个位置
ph[k]=j 表示第k个插入的数在堆里面的下标是j
hp(heap->point)可以获得在堆的第n个元素存的是第几个插入的元素
hp[j]=k表示堆里下标是j的点 对应的是第k个插入的数
这两个数组是互逆的
那这样的话 交换元素就不能只换两个值 还要映射关系也同步一下
// 堆的全新的交换方式
void heap_swap(int a, int b){
//先由hp找到对应的插入次序，然后交换ph数组中记录的两个元素的下标
swap(ph[hp[a]], ph[hp[b]]);
swap(hp[a], hp[b]); //交换hp数组中记录的两个元素的插入次序
swap(h[a], h[b]); // 最后交换堆中的两个元素
}
其他地方无需变动什么 把swap替换成这里的heap_swap即可
因为要交换1 2结点中的值 物理位置还是不变的
所以只要更新关系就行
要先通过hp找到是第几个插入的数
再根据这个得到的下标更新ph中的指向
然后再同步hp
最后才进行真正的值交换
//先由hp找到对应的插入次序，然后交换ph数组中记录的两个元素的下标
swap(ph[hp[a]], ph[hp[b]]);
//交换hp数组中记录的两个元素的插入次序
swap(hp[a], hp[b]);
// 最后交换堆中的两个元素
swap(h[a], h[b]);
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int h[N], mysize;//原本逻辑不变
int ph[N], hp[N];//加两个数组去维护映射关系
void heap_swap(int a, int b)
{
//先由hp找到对应的插入次序，然后交换ph数组中记录的两个元素的下标
swap(ph[hp[a]],ph[hp[b]]);
//交换hp数组中记录的两个元素的插入次序
swap(hp[a],hp[b]);
// 最后交换堆中的两个元素
swap(h[a],h[b]);
}
void down(int x)
{//基本一样 就是把swap变成了heap_swap
int t = x;
if (x * 2 <= mysize && h[x * 2] < h[t])
t = x * 2;
if (x * 2 + 1 <= mysize && h[x * 2 + 1] < h[t])
t = x * 2 + 1;
if (x != t)
{
heap_swap(x, t);
down(t);
}
}
void up(int u)
{//基本一样 就是把swap变成了heap_swap
if(u/2 && h[u]<h[u/2])
{
heap_swap(u, u / 2);
up(u>>1);
}
}
int main()
{
int n, m = 0;//m表示当前第几个插入的数
scanf("%d", &n);
while (n -- )
{
char op[5];
int k, x;
scanf("%s", op);
//插入一个数 x
if (!strcmp(op, "I"))
{
scanf("%d", &x);
mysize ++ ;
m ++ ;
//加上这里两句 第m个插入的数为堆（数组）中最新添加的 然后反过来存一下最新添加为第m个数
ph[m] = mysize, hp[mysize] = m;
//逻辑一样 还是在最后插 然后向上调整这个数
h[mysize] = x;
up(mysize);
}
//输出当前集合中的最小值
else if (!strcmp(op, "PM"))
cout<<h[1]<<endl;//取堆顶即可
//删除当前集合中的最小值
else if (!strcmp(op, "DM"))
{//逻辑不变 把最后一个数换上来 删最后一个数 向下调整它
heap_swap(1, mysize);//变的就是swap函数
mysize -- ;
down(1);
}
//删除第 k个插入的数
else if (!strcmp(op, "D"))
{
//同理 把最后一个元素换一下 删最后 然后向上向下调整（只会执行一个）
scanf("%d", &k);
k = ph[k];//找到第k个数在堆中的位置
heap_swap(k, mysize);
mysize -- ;
up(k);
down(k);
}
//修改第 k个插入的数，将其变为 x
else
{//找到位置后 修改值 向上向下调整即可
scanf("%d%d", &k, &x);
k = ph[k];//找到第k个数在堆中的位置
h[k] = x;
up(k);
down(k);
}
}
return 0;
}
💬 评论