【习题解答】 堆与偏序关系

注： 本题解为个人完成，难免有疏漏，请勿抄袭，仅供参考，同时欢迎留言指正。 ## 14.1 + 是第h个节点的父节点 + 是第h个节点的层数 + 是第h个节点的父节点的层数 + ，因为的层数比父节点的层数多一层

14.2

取堆的前层即可，找第大的数，复杂度，和无关

14.3

D-ARY-PARENT

用数学归纳法证明： + 基本情况：，父节点是 + 归纳推理：设时，父节点是成立，则对于，父节点是也成立 + 故i节点的父亲节点是

D-ARY-CHILD

可以还用数学归纳法，当然也可以直接父节点的结论。

考虑节点的父节点是

节点的父节点是

因此的第一个子节点是，故的第个子节点是

14.4

只给思路： + 首先用数学归纳法证明节点数为(为非负整数)时，高度和恰为 + 然后考虑的情况，多出节点x个，高度和多出 + 因此若节点数为，则高度和最多为

14.5

用分治的思路即可： + 先把数组二分，解决两个子问题 + 然后合并链表即可

复杂度分析：

注：本题同4.8的思路，如果用堆的方法也可以。

14.6

只给思路：

• 利用两个元素规模最多差1的堆结构，分别为最大堆和最小堆，其中最大堆的堆顶比最小堆的堆顶小。
• 通过维护这样的结构，可以在常数时间查出中位数，并且插入、删除都是对数时间代价。
• 详细算法表述从略。主要需注意维护两个堆的规模大小，始终最多差1个元素。