题目描述
这题 可能比较难 理解的是hp,与ph; 其实就是插入次序 和下标的相互 映射
这里我做个解释吧:
hp[i]=k; (h–>p) –表示 下标i 对应的元素 h[i] 插入次序 k
ph[k]=i;(p–>h)–表示 插入次序k 对应的元素 h[ph[k]]下标 为i
//其他细节见代码注释 QAQ
样例
#include<iostream>
#include<algorithm>
#include<string.h> //注意 这里不能 用<string>-->//表示类. 可以用<cstring>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int h[N], ph[N], hp[N], h_size;
// hp[j] -- 给下标 j 找次序 k
//ph[k] -- 给次序 k 找下标 i ph[k]=i; hp[i]=k; --像反函数 j下标,k是第k个插入的位置
// // ph[] --映射的下标i、j hp[]映射的是下标i,j输入的元素 是插入次序 k(第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]); //交换值
}
//易错 down 这里是小于 h_size 而不是n
void down(int k)
{
int t = k;
if (2 * k <= h_size && h[2 * k] < h[t]) t = 2 * k;
if (2 * k+1 <= h_size && h[2 * k+1] < h[t]) t = 2 * k+1;
if (k != t)
{
heap_swap(k,t);
down(t);
}
}
void up(int k)
{
// 需要保证父节点存在 ,最小为1 --还可以取
while(k/2 && h[k/2]>h[k] ) //向上 与 他的 父节点 比较,如果父节点比他大,就交换hp 和 ph,还有下标
{
heap_swap(k/2,k);
k /= 2; //现在他是父节点了-- 继续递归找他的上上个父节点 是否还比他大
}
}
int main()
{
cin >> n;
while (n--)
{
char op[10];
int k, x;
cin >> op;
if (!strcmp(op, "I")) // strcmp--如果字符串 相同 返回0 ,str1< str2 返回小于0的int, str1> str2--返回大于1的int
{
cin >> x;
h_size++;
m++;
ph[m] = h_size, hp[h_size] = m;
h[h_size] = x;
up(h_size);
}
else if (!strcmp(op, "PM")) printf("%d\n", h[1]);
else if (!strcmp(op,"DM"))
{
heap_swap(h_size,1);
h_size--;
down(1);
}
else if (!strcmp(op, "D"))
{
cin >> k;
k = ph[k]; //找到 第k个插入 元素的下标 ph[k]
heap_swap(k,h_size );
h_size--;
down(k), up(k); //也是对下标执行
}
else
{
cin >> k >> x;
k = ph[k];
h[k] = x;
down(k), up(k);
}
}
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla