이중 우선순위 큐

• Double-ended priority queue 를 만드는 문제.
• 링크에서 설명했듯이 다양한 방법이 있지만, 여기에서는 가장 심플한 방법인 min heap과 max heap을 UpdatableHeap로 만들어서 사용했다.
• n번의 삽입 삭제가 일어날때, 각각은 O(logn)에 처리되니 총 시간 복잡도는 O(nlogn).
• 그러나 실제 제출된 코드들을 보면, 그냥 deque를 정렬된 상태로 유지해서, 삽입을 O(n)으로 처리하는 코드가 시간복잡도는 느리지만 더 빠르게 동작했다.;

"""Solution code for "BOJ 7662. 이중 우선순위 큐".

- Problem link: https://www.acmicpc.net/problem/7662
- Solution link: http://www.teferi.net/ps/problems/boj/7662
"""

import sys
from teflib import priorityqueue


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        max_heap = priorityqueue.UpdatableHeap()
        min_heap = priorityqueue.UpdatableHeap()
        k = int(sys.stdin.readline())
        for _ in range(k):
            op, n = sys.stdin.readline().split()
            if op == 'I':
                num = int(n)
                max_heap.push(-num)
                min_heap.push(num)
            elif max_heap:
                if n == '1':
                    num = -max_heap.pop()
                    min_heap.delete(num)
                elif n == '-1':
                    num = min_heap.pop()
                    max_heap.delete(-num)
        if max_heap:
            print(-max_heap.top(), min_heap.top())
        else:
            print('EMPTY')


if __name__ == '__main__':
    main()

• Dependency: teflib.priorityqueue.UpdatableHeap