问题
如何理解AcWing 模拟堆这道题中的heap_swap，hp[N], ph[N]？
详解
重点：题目中第k个插入，这里的k相当于链表中的idx，是节点的唯一标识
不理解idx到底是啥意思的可以先看看这篇，其中总结了对链表，Trie树，堆中idx的理解：https://www.acwing.com/solution/content/5673/
- 关于idx
堆中的每次插入都是在堆尾，但是堆中经常有up和down操作。所以节点与节点的关系并不是用一个ne[idx][2]可以很好地维护的。但是好在堆是个完全二叉树。子父节点的关系可以通过下标来联系（左儿子2n，右儿子2n+1）。就数组模拟来说，知道数组的下标就知道结点在堆中的位置。所以核心就在于即使有down和up操作也能维护堆数组的下标（k）和结点（idx）的映射关系。 比如说：h[k] = x, h数组存的是节点的值，按理来说应该h[idx]来存，但是节点位置总是在变的，因此维护k和idx的映射关系就好啦
举例： 用ph数组来表示ph[idx] = k(idx到下标), 那么结点值为h[ph[idx]], 儿子为ph[idx] * 2和ph[idx] * 2 + 1, 这样值和儿子结点不就可以通过idx联系在一起了吗？
- 理解hp与ph数组
从上面讨论的可以知道，ph数组主要用于帮助从idx映射到下标k，似乎有了ph数组就可以完成所有操作了，但为什么还要有一个hp数组呢？
原因就在于在swap操作中我们输入是堆数组的下标，无法知道每个堆数组的k下标对应idx（第idx个插入），所以需要hp数组方便查找idx。
void heap_swap(int a, int b) { swap(ph[hp[a]], ph[hp[b]]); swap(hp[a], hp[b]); swap(h[a], h[b]); }
3. 举例：堆中的插入操作
注意： 在堆这个数据结构中，数据的插入都是插入到堆尾，然后再up
if (op == “I”) { scanf(“%d”, &x); size ++ ; idx ++ ; //记录第几次插入（设置新的idx） ph[idx] = size, hp[size] = idx; //每次插入都是在堆尾插入（设置ph与hp） h[ph[idx]] = x; //记录插入的值 up(ph[idx]); }
4. 举例：删除第idx个插入元素
删除操作，三个步骤：
- 找到第idx个插入元素在堆数组中的位置（堆数组下标）
- 与堆尾元素交换
- 在原来第idx个元素所在的位置进行down和up操作。（up，down，swap操作的都输入都是下标）
很显然，在第一步中，显然ph[idx]查找即可。第二步，直接swap操作。第三步需要找到原来第idx的元素所在的位置，由于交换完后ph[idx]的值变了，变为堆尾的下标了，所以必须要在之前保存ph[idx]的值
if (op == “D”) { scanf(“%d”, &idx); k = ph[idx]; //必须要保存当前被删除结点的下标 heap_swap(k, size);//第idx个插入的元素移到了堆尾，此时ph[idx]指向堆尾 size --; //删除堆尾 up(k);//k是之前记录被删除的结点的下标 down(k); }
38 评论
提交评论
13333409541 4个月前 3 回复
/*
1、理解hp与ph数组，以及为什么需要它们
- 堆h[i]只能存放数据，不能存放是第几个数字，所以需要ph[k] = i来指明，第k个数字在h[]中对应的i是多少
- 在执行交换操作的时候，可以直接交换数字,swap(h[a],h[b])
但是对于ph[k_1] = a和ph[k_2] = b来说，a和b是它们存放的值，不 能通过值来找下标，也就是找不k_1,k_2是多少 - 于是引入hp[a] = k_2，hp[b] = k_2，则可以实现反向的操作
2、形象理解heap_swap中的次序是任意的
h[]：房间号无直接实际意义，里边住着犯人
ph[]：花名册，狱警所有，写明了几号犯人住在哪个房间号里，用于抓某些人
（但是狱警无权过问每个号里住的是谁）
hp[]：住户册，监狱所有，写明了哪个房间号里住的是几号，用于管理监狱
（但是监狱没必要知道哪个犯人住在哪里）
heap_swap：已知两个犯人住的地方，交换它们住的地方，并且让狱警和管理 处都知道这件事情
swap(h[a], h[b])：两个人换地方住
swap(hp[a], hp[b])：监狱管理处翻房间号，把里边存放的犯人号交换
swap(ph[hp[a]], ph[hp[b]])：狱警：先申请查住户册，看这两个地方住的谁，再在花名册下写下来，这两个人位置换了
h[a] = 10, h[b] = 20 swap: h[a] = 20,h [b] = 10
hp[a] = 1 ,hp[b] = 2 swap:hp[a] = 2 ,hp[b] = 1
ph[1] = a ,ph[2] = b swap:ph[1] = b ,ph[2] = a
//这种不变形也很像线代中：代表交换的初等矩阵，进行逆运算之后，仍然是该初等矩阵
