1. 计算数据流的中位数

中位数是将一个数据集分成数量相等的上下两部分的值。我们的核心思想就是维护这两个“部分”。

核心思想：双堆

我们使用两个堆来模拟被中位数分开的数据集：

1. 一个大顶堆 (Max-Heap) small_half: 用于存储数据流中较小的那一半数字。堆顶是这一半数据中的最大值。
2. 一个小顶堆 (Min-Heap) large_half: 用于存储数据流中较大的那一半数字。堆顶是这一半数据中的最小值。

为了让这两个堆能够正确地“分割”数据流，我们必须始终维持两个不变的规则：

1. 大小平衡: 两个堆的大小要么相等，要么大顶堆 small_half 比小顶堆 large_half 多一个元素。这样可以确保中位数总是在两个堆的顶部产生。
2. 数值关系: 大顶堆 small_half 中的所有元素都必须小于或等于小顶堆 large_half 中的所有元素。

算法步骤

每当一个新的数据 num 到来时，我们执行以下步骤：

1. 插入新元素:
   • 先将 num 推入大顶堆 small_half。
   • 为了维持数值关系规则，我们立即将 small_half 的堆顶元素（即较小一半中的最大值）弹出，并推入小顶堆 large_half。
   • 经过这两步，num 已经被正确地分配到了两个堆中的某一个，并且数值关系规则得到了保证。但大小平衡可能被打破。
2. 重新平衡堆的大小:
   • 在插入后，检查两个堆的大小。如果小顶堆 large_half 的大小超过了大顶堆 small_half，说明 large_half "偷"走了一个元素。
   • 我们将 large_half 的堆顶元素（即较大一半中的最小值）弹出，并推入 small_half，恢复大小平衡。
3. 计算当前中位数:
   • 如果两个堆大小相等 (数据总数为偶数)，中位数就是两个堆顶元素的平均值：(small_half.top() + large_half.top()) / 2.0。
   • 如果大顶堆 small_half 比小顶堆 large_half 多一个元素 (数据总数为奇数)，中位数就是 small_half 的堆顶元素。

2. 计算数据流的百分位数

计算百分位数（例如，第90百分位数）的思想与中位数（第50百分位数）完全相同，只是大小平衡的规则发生了改变。

核心思想：按比例划分

对于第 p 百分位数，需要将数据流划分为：

• 底部 p% 的数据: 用一个大顶堆 small_group 维护。
• 顶部 (100-p)% 的数据: 用一个小顶堆 large_group 维护。

第 p 百分位数就是 small_group 的堆顶元素。

算法步骤

设当前已处理的数据总数为 N，要计算第 p 百分位数。

1. 插入新元素: 与中位数算法的插入步骤完全相同。
   • small_group.push(num)
   • large_group.push(small_group.top()); small_group.pop()
2. 重新平衡堆的大小 (按比例):
   • 这是与中位数算法唯一的不同点。
   • 我们的目标是让 small_group 的大小 k 约等于 N * (p / 100.0)。
   • 更精确地，我们希望 small_group 的大小为 k = ceil(N * p / 100.0)。ceil 是向上取整函数。
   • 循环调整：
     • 当 small_group.size() > k 时，不断从 small_group 弹出堆顶元素并推入 large_group，直到 small_group.size() == k。
     • 当 small_group.size() < k 时，不断从 large_group 弹出堆顶元素并推入 small_group，直到 small_group.size() == k。
3. 计算当前百分位数:
   • 调整完毕后，第 p 百分位数就是 small_group 的堆顶元素 small_group.top()。