数据结构: 对顶堆

对顶堆

• 对顶堆是用于解决寻找序列中第k小数的数据结构，其中序列可动态变化、k可动态变化 对顶堆较易实现，比实现权值线段树、平衡树有码量上的优势

• 基本组成：一个大顶堆和一个小顶堆(辅助堆)，大顶堆维护前k小的元素(包括k)，小顶堆维护其它元素(即比第k元素大的元素)

  这样，大顶堆的堆顶就是第k个元素、小顶堆的堆顶是第k + 1个元素 如果要求寻找序列中第k大的数，则反过来用小顶堆维护前k大的元素、用大顶堆作辅助堆即可

• 每次涉及到动态修改(如插入、修改k值)，需要在操作结束后维护： 若大顶堆元素超出k个，则将大顶堆的堆顶弹出后插入小顶堆中 否则将小顶堆堆顶插入大顶堆中

• 插入元素：若插入元素不小于大顶堆堆顶，则插入小顶堆中，否则插入大顶堆中

• 查询第k小元素：返回大顶堆堆顶

• 删除第k小元素：推出大顶堆堆顶和小顶堆堆顶，将后者插入大顶堆中

• 动态修改k值：与维护操作描述一致，若k增大，则推出小顶堆堆顶插入大顶堆中；否则推出大顶堆堆顶插入小顶堆中

• 时间复杂度：查询O(1)，其余操作O(logn)