对顶堆

· · 个人记录

动态维护第k大

小根堆q1,大根堆q2

核心：让两堆分别存一大一小的可能答案

insert(x):
if(x>=q1.top() || q1.empty()) q1.push(x);
else q2.push(x);

while(q1.size()>k) q2.push(q1.top()),q1.pop();
while(q1.size()<k) q1.push(q2.top()),q2.pop();

query(k)=q1.top();

动态求中位数