您的位置: 首页 > 文章 > 随时确定中位数

随时确定中位数

分类: 文章 • 2025-02-01 09:31:52

随时确定中位数

思路：

设置一个大根堆和一个小根堆，大根堆力求存储N/2部分的小值，小根堆力求存储N/2部分的大值，保持此状态后，哪个堆的值多则中位数就是哪个堆的堆顶元素。

如何保持均衡分布？

每次进入的值和大根堆的堆顶元素比较，当其值大于大根堆时，进入小根堆，当两者的值相差大于等于2时，多的一个堆出堆顶元素赋值给小的堆。、

整个过程对于python可以使用heapq简易实现。