--- title: "模拟堆" created: 2025-11-28 tags: - 算法 --- # 模拟堆 ## 题目 [模拟堆](https://www.acwing.com/problem/content/841/) ![[image-7b0d9d3b.png]] ## 思路分析 其实考虑的就是 如果要对第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即可 ![[image-30dc4b42.png]] 因为要交换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]); ## 代码实现 ```cpp #include 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]>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<