对顶堆

基本方法: 将最小的一半元素放到大根堆里面去, 将最大的一半元素放到小根堆里面去.
具体的方法:
1. 新的元素比较一下与小根堆堆顶元素的关系, 如果相等或者新元素更大, 放到小根堆里面去, 否则, 放到大根堆里面去.
2. 观察一下小根堆的大小是否符合要求, 如果不符合, 与大根堆交换元素, 最多交换一个元素.
3. 当动态数据长度为奇数时, 小根堆的堆顶就是要求的中位数.

时间复杂度

O(n*log(n)

Python 代码

from heapq import heappop, heappush

def solve(idx, A):
    M = len(A)
    if M == 1:
        print(idx, 1)
        print(A[0])
        return

    print(idx, (M + 1) // 2)
    ans = []
    ans.append(A[0])
    if A[0] <= A[1]:
        small, big = [-A[0]], [A[1]]
    else:
        small, big = [-A[1]], [A[0]]
    for i in range(2, M):
        n = i + 1
        n_small = n // 2
        e = A[i]
        if e >= big[0]:
            heappush(big, e)
        else:
            heappush(small, -e)
        if len(small) < n_small:
            tmp = heappop(big)
            heappush(small, -tmp)
        elif len(small) > n_small:
            tmp = heappop(small)
            heappush(big, -tmp)
        if n % 2:
            ans.append(big[0])
    #print(ans)

    for i in range(len(ans)):
        if i % 10 != 9:
            print(ans[i], end=" ")
        else:
            print(ans[i])
    if len(ans) % 10:
        print()

P = int(input())
for _ in range(P):
    idx, M = map(int, input().split())
    A = []
    while len(A) < M:
        sub_A = list(map(int, input().split()))
        A.extend(sub_A)
    solve(idx, A)