模拟堆详解

代码解析

h[N]：用于存储堆中的元素。

ph[N]：存储第 k 个插入的元素在堆中的位置（eg:ph[k] = i，表示将第 k 个插入的元素在 h[i] 中）。

hp[N]：存储堆中第 i 个元素是第几个插入的（eg:hp[i] = k，表示 h[i] 是第 k 个插入的元素）。

cnt：当前堆中元素的数量。

m：记录插入操作的总次数。

heap_swap 函数

通过 ph 和 hp 数组实现了堆中元素的索引映射，可以使我们在堆中快速定位和修改特定元素。

功能：交换堆中的两个元素，并更新 ph 和 hp 数组。

实现：

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

交换 ph[hp[a]] 和 ph[hp[b]]。

交换 hp[a] 和 hp[b]。

交换 h[a] 和 h[b]。

简单理解heap交换映射的逻辑：

假设小明和小红 要互换住址，居委会那边可以查小明和小红的住址【ph】，同时小明身上的身份证【hp】用于修改地址 小红同理。那么搬家该怎么搬呢，
首先 小明小红 先去居委会出示了 身份证 swap(ph[hp[小明]],ph[hp[小红]）更换了户口，
户口换完了 当然的身份证信息也要修改啦~swap(hp[小红],ph[小明])，
最后俩人找来搬家公司 搬完了东西 最后顺利入住了 swap(小明，小红)

简单理解来自种花家的鸭脖 

down 函数

向下调整堆，确保以 u 为根的子树满足小根堆的性质。

up 函数

向上调整堆，确保以 u 为根的子树满足小根堆的性质。

strcmp 函数

strcmp  是 C 和 C++ 标准库中的一个字符串比较函数，用于比较两个以空字符（ \0 ）结尾的字节字符串。它定义在头文件  <cstring> （C++）或  <string.h> （C）中。

比较规则 ：strcmp  按字典序比较两个字符串，逐个字符进行比较，直到遇到不同的字符或字符串结束符  \0 。比较时，字符的大小是根据它们的 ASCII 值来确定的。

返回值 < 0：表示  str1  小于  str2 。

返回值 == 0：表示  str1  和  str2  相等。

返回值 > 0：表示  str1  大于  str2 。

AC代码

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int N=100010;
int h[N],ph[N],hp[N],cnt;
//ph表示第k个插入的数在堆中的位置，hp表示堆中位置k对应的是第几个插入的数
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]){//完全二叉树[n/2]处是最后一个非叶子节点heap_swap(u,u/2);u>>=1;}
}
int main()
{int n, m = 0;cin>>n;while (n -- ){char op[5];int k, x;cin>>op;if (!strcmp(op, "I")){cin>>x;cnt ++ ;m ++ ;ph[m] = cnt, hp[cnt] = m;h[cnt] = x;up(cnt);}else if(!strcmp(op, "PM")) cout<<h[1]<<endl;else if(!strcmp(op, "DM")){heap_swap(1, cnt);cnt -- ;down(1);}else if (!strcmp(op, "D")){cin>>k;k = ph[k];heap_swap(k, cnt);cnt -- ;up(k);down(k);}else{cin>>k>>x;k = ph[k];h[k] = x;up(k);down(k);}}return 0;
}