数据结构 堆

例题——模拟堆[包含映射]

增加两个数组

使用两个数组维护两个映射关系，ph[k] 存第k个插入的点在堆中的下标，hp[k] 存堆中下标为k的点是第几个插入的点

增加的原因

因为按第几个插入元素更改内容，需要知道第i个插入的元素在堆中的下标，所以需要ph的存在，而因为元素在进行down与up操作时，使得ph内容与实际堆的元素不对应，所以要改变ph，而改变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]);

return;

}

交换堆中的两个元素时，hp 和 ph 也改变。先改变 hp 和 ph 中的内容，然后改变这两个结点中的值。先根据交换的下标找到对应的 hp，并以两个 hp 元素值作为 ph 的下标，交换这2个 ph 元素值。之后根据下标交换 hp。

swap(ph[hp[a]], ph[hp[b]])；为什么这里的ph的下标是hp的元素值而不是堆中元素的编号？

因为ph的下标k的含义【即ph[k]的k的含义】是第k个插入的点，所以我们要找到第k个插入的点而不是堆中下标为k的点。

改变后的操作

up 操作

手写的heap_swap函数代替原来的swap函数

void up(int u) {

while (u / 2 && h[u / 2] > h[u]) {//u的父结点为u/2,父结点存在且大于本身，交换

heap_swap(u / 2, u);

u = u / 2;

}

return;

}

down 操作

手写的heap_swap函数代替原来的swap函数

void down(int u) {

int t = u;//用t表示三个点中的最小值

if (u * 2 <= size1 && h[u * 2] < h[t])//先判断是否有左儿子，然后判断左儿子是否小于其本身,如果成立，交换

t = u * 2;

if (u * 2 + 1 <= size1 && h[u * 2 + 1] < h[t])//再判断是否有右儿子，然后判断右儿子是否小于其本身,如果成立，交换

t = u * 2 + 1;

//最终，t存的就是三个点中最小的结点编号

if (u != t) {//如果u!=t，说明根结点就不是最小的，需要交换

heap_swap(u, t);//交换

down(t);

}

return;

}

向集合中插入一个数

添加hp和ph数组中的映射关系

scanf("%d", &x); //向堆中插入x

size1++;

m++;

ph[m] = size1;

hp[size1] = m;

h[size1] = x;

up(size1);

输出集合中的最小值

printf("%d\n", h[1])

删除最小值

手写的heap_swap函数代替原来的swap函数

heap_swap(1, size1);

size1--;

down(1);

删除第k个插入的元素

scanf("%d", &k);//输入k

k = ph[k];//找到第k个插入的元素在堆中的下标，然会对其进行删除

heap_swap(k, size1);//用堆中最后一个元素覆盖找到的元素，然会进行调整

size1--;

down(k), up(k);

修改第k个插入的元素

scanf("%d%d", &k, &x);//输入k和修改后的值x

k = ph[k];//找到第k个插入的元素在堆中的下标，然后修改其值，修改后进行调整

h[k] = x;

down(k), up(k);

题目描述

维护一个集合，初始时集合为空，支持如下几种操作：

“I x”，插入一个数x；

“PM”，输出当前集合中的最小值；

“DM”，删除当前集合中的最小值（当最小值不唯一时，删除最早插入的最小值）；

“D k”，删除第k个插入的数；

“C k x”，修改第k个插入的数，将其变为x；

现在要进行N次操作，对于所有第2个操作，输出当前集合的最小值。

输入格式

第一行包含整数N。

接下来N行，每行包含一个操作指令，操作指令为”I x”，”PM”，”DM”，”D k”或”C k x”中的一种。

输出格式

对于每个输出指令“PM”，输出一个结果，表示当前集合中的最小值。

每个结果占一行。

数据范围

1≤N≤10^5

−10^9≤x≤10^9

数据保证合法。

输入样例

8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM

输出样例

-10
6

#include

#include

#include

using namespace std;

const int N = 100010;

int h[N], ph[N], hp[N], size1;//h[N]就是heap[N],size1存储当前有多少个元素,ph[k]存第k个插入数组的下标

//ph[j]=k【第j次插入数组的数的下标是k】,hp[k]=j【下标为k的数是第j次插入数组中的数】

void heap_swap(int a, int b) {

swap(ph[hp[a]], ph[hp[b]]);//交换指向

swap(hp[a], hp[b]);

swap(h[a], h[b]);

return;

}

void down(int u) {

int t = u;//用t表示三个点中的最小值

if (u * 2 <= size1 && h[u * 2] < h[t])//先判断是否有左儿子，然后判断左儿子是否小于其本身,如果成立，交换

t = u * 2;

if (u * 2 + 1 <= size1 && h[u * 2 + 1] < h[t])//再判断是否有右儿子，然后判断右儿子是否小于其本身,如果成立，交换

t = u * 2 + 1;

//最终，t存的就是三个点中最小的结点编号

if (u != t) {//如果u!=t，说明根结点就不是最小的，需要交换

heap_swap(u, t);//交换

down(t);

}

return;

}

void up(int u) {

while (u / 2 && h[u / 2] > h[u]) {//u的父结点为u/2,父结点存在且大于本身，交换

heap_swap(u / 2, u);

u = u / 2;

}

return;

}

int main() {

int n, m = 0;

scanf("%d", &n);

while (n--) {

char op[10];

int k, x;

scanf("%s", op);

if (!strcmp(op, "I")) {

scanf("%d", &x);

size1++;

m++;

ph[m] = size1;

hp[size1] = m;

h[size1] = x;

up(size1);

}

else if (!strcmp(op, "PM"))

printf("%d\n", h[1]);

else if (!strcmp(op, "DM")) {

heap_swap(1, size1);

size1--;

down(1);

}

else if (!strcmp(op, "D")) {

scanf("%d", &k);

k = ph[k];

heap_swap(k, size1);

size1--;

down(k), up(k);

}

else {

scanf("%d%d", &k, &x);

k = ph[k];

h[k] = x;

down(k), up(k);

}

}

return 0;

}