우선순위 큐에서 원소를 삭제하는 테크닉

오늘 수업 때 배운 테크닉인데, 상당히 간단하고 또 범용적이어서 한번 정리해볼까 한다.

 

원하는 원소들 중 최소, 최대를 관리해주고 싶으면, 우선순위 큐라는 자료구조를 사용할 수 있다. 하지만 원소를 삭제하고 싶다면 어떻게 해야할까?

 

가장 쉽게 생각할 수 있는 방법은 세그먼트 트리를 사용하는 것이다. 하지만 상수가 크고, 메모리도 더 잡아먹기에 추천하지 않는다. 

 

현재 있는 원소와 삭제된 원소를 담아주는 우선순위 큐 2개를 관리해줄 것이다.

삽입 연산은 그냥 해주면 되고, 삭제 연산은 삭제된 원소를 담아주는 큐에 push해주면 된다.

top을 볼 때는 삭제된 원소를 관리해주는 큐와 그냥 큐의 top을 비교해주며, 만약 같다면 둘다 pop해주고, 다르면 그냥 큐의 top이 우리가 원하는 top 값이 된다.

큐의 크기를 알고 싶다면, len(현재큐) - len(삭제큐)를 return해주면 된다.

 

왜 그럴까? top에서 뽑히는 원소는 1. 삭제되지 않은 원소 or 2. 삭제된 원소 둘 중 하나일텐데, 삭제되지 않은 원소가 top인 경우에는 삭제큐에 그 원소가 있을 수가 없고, 만약 삭제된 원소라면 삭제큐의 최소와 현재큐의 최소는 같을 것이기 떄문이다. 원소의 중복이 있어도 사용 가능함은 쉽게 알 수 있다.

 

파이썬에서 구현한바는 다음과 같다.

from heapq import heappop, heappush

class DelPq:
    def __init__(self):
        self.q = []
        self.er = []

    def top(self):
        while self.q and self.er and self.er[0] == self.q[0]:
            heappop(self.q)
            heappop(self.er)
        return self.q[0]

    def insert(self, v):
        heappush(self.q, v)

    def delete(self, v):
        heappush(self.er, v)

    def __len__(self):
        return len(self.q) - len(self.er)

정말 간단하고 아름다운 테크닉인 것 같다.