二叉堆计算动态中位数

要求

最近在刷算法,遇到一个有意思的题,要求如下:

设计一个数据结构,可随时插入节点,且随时查询节点集合的中位数,要求插入节点的时间复杂度为 O(logN),查询中位数的时间复杂度为 O(1)。

中位数定义:节点个数为奇数个时,为有序情况下集合的中间节点;偶数时,为中间两节点的平均值。

[……]

阅读全文