随时确定中位数

    科技2022-08-06  128

    思路:

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

    如何保持均衡分布?

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

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

    Processed: 0.009, SQL: 8