问题求解II-HW10 题解
Problem A: 堆
给定框架代码，补全堆实现的 heapify, top, pop, make_heap 等函数。
模板题。在代码实现上的技巧是：使用数组 (1-base) 存储完全二叉树时，下标 $x$ 元素的父亲节点下标是 $\lfloor \frac{x}{2}\rfloor$，左孩子下标是 $2x$，右孩子下标是 $2x+1$。
Problem B: 动态中位数
- 给定 $n$ 个数，对于每个 $1\leq i\leq n$ 输出前 $i$ 个数的中位数。
- $n\leq 10^5$。
考虑使用一个大根堆和一个小根堆来维护动态中位数。我们将 $n$ 个数依次插入，每次插入时根据它和小根堆最大数的大小关系决定一下它应该去哪个队。插入完毕后再调整一下两个堆的大小，保证数的个数差始终在1以内。如此维护，每次只需要根据小根堆最大数和大根堆最小数计算中位数即可。总时间复杂度 $O(n\log n)$。