우선순위큐에서 임의 요소 삭제하기

우선순위큐(priority queue) 자료구조는 추상적인 개념으로, 반드시 힙(heap)을 이용해 구현할 필요는 없지만 일반적으로는 힙을 이용해 구현한다.

힙을 이용하여 우선순위큐를 구현하게 될 경우 요소를 삽입(push)할 때 O(log N)의 시간복잡도를 가지고, 우선순위가 가장 높은 요소를 확인(top)하는 것은 O(1)이지만 이를 삭제(pop)하는 연산에는 O(log N)이 걸린다. 여기서 우선순위가 가장 높은 요소 1개를 확인하거나 삭제할 수 있다는 점에 주목하라. 우선순위큐의 특성상 그 외의 우선순위가 낮은 요소들은 확인하거나 삭제할 방법이 없다.

이러한 상황 속에서, 우선순위큐에 들어있는 어떤 임의의 요소를 삭제하는 상황이 생겼다고 하자. 이는 어떻게 처리하면 좋을까?

만약 우선순위큐에 들어가는 수의 범위가 충분히 작다는 것이 보장된다면 카운팅 배열을 만들어서 해결이 가능하다. 가령, 위의 그림처럼 7을 삭제하는 요청이 들어오면 chk[7]++ 처럼 기록하는 것. 그 후 나중에 top을 봤더니 chk 배열에 체크된 상태라면 이미 삭제된 요소로 간주하는 것이다. 하지만 세상은 그리 녹록지 않다. 일반적인 상황으로 32 bit integer가 들어온다고 생각해보자(물론 좌표압축해서 기어이 카운팅으로 풀려는 사람은 말리지 않겠다. 근데 이건 오프라인에서나 가능하잖아? 좀 더 일반적인 상황을 생각해보자고, 친구).

그러한 상황에 대해서는 배열이나 리스트 등을 이용해서 삭제하는 요소를 따로 기록해두고, 만약 top이 기록된 요소였다면 우선순위큐 및 기록에서 삭제하는 방법을 생각해볼 수 있겠다. 하지만 단순히 배열(혹은 리스트)에 기록하면 매번 기록된 모든 요소를 확인해야 하는 수고가 생기며, 기록된 요소를 순회하는 데 O(N^2)만큼 들기 때문에 느려터졌다고 손가락질 받기 딱 좋다. 더 좋은 방법은 없을까?

배열 대신 우선순위큐를 이용하여 삭제할 요소를 기록하면 된다!!!

3, 5, 7을 삭제하는 요청이 생겨서 이를 별도의 우선순위큐에 기록한 그림이다. 왼쪽의 기존 우선순위큐를 A, 오른쪽의 기록용 우선순위큐를 B라고 하면 A의 top을 사용하기 전에 B의 top과 비교하여 같지 않을 때까지 A, B에서 pop해주는 것이다. 삭제 요청이 들어올 때마다 삭제를 처리하는 것이 아닌, 일단 기록해두고 나중에 필요할 때 삭제를 해준다는 점에서 lazy하다고 볼 수 있다.

이 방법을 이용하면 일반적인 모든 상황에 대해 대처가 가능할까?

Q1. 중복된 원소가 있어도 가능함?

A1. 당연히 가능. 중복은 전혀 문제될 사항이 아니다. 생각을 좀 해라.

Q2. 기존의 우선순위큐에 존재하지 않는 요소를 삭제하는 요청이 들어와도 쌉가능?

A2. 이건 위의 질문보다 퀄리티가 좋다. 여기서 A에 존재하지 않는 요소 x를 삭제하는 요청이 들어왔다고 생각해보자. 이 x가 B에 들어갔을 때, 문제가 되는 상황은 x가 B의 top에 위치하여 실질적인 비교를 방해하는 상황이다(만약 x의 우선순위가 다른 요소보다 낮다면 그 아래 구석 어딘가에 처박혀 있을 것이기 때문에 무시가 가능하다). 이 상황에 대해서는 B의 top이 A의 top보다 우선순위가 높은 경우 B에서만 계속 pop해주면 된다. 그러면 더 이상 비교를 방해하는 x들은 B에 없게 되거나 구석 어딘가에 처박혀 있어서 방해를 하고 싶어도 못 하게 된다.

우리는 이제 이 방법으로 우선순위큐에서 임의의 요소를 삭제하는 요청까지 O(log N)으로 깔끔하게 처리를 할 수 있게 되었다.