쓰이는 알고리즘 - 우선순위 큐(Heap)의 임의 요소 삭제에 관한 Idea

최소 혹은 최대값 찾기에 최적화된 힙에서 임의 요소를 삭제하고 싶다면?

 

 

우선순위 큐는 반드시 Heap으로 구현할 필요는 없지만, 최소 혹은 최대값에 focus를 두는 우선순위 큐의 특성 상 일반적으로 그 장점을 최대한 잘 살릴 수 있는 Heap을 이용하여 구현한다.

 

하지만 Heap을 이용하여 우선순위 큐를 구현하게 되면 임의의 요소를 삭제하는 case를 처리하기 곤란해진다. 본 포스팅에선 이런 상황에서 도움이 될만한 idea를 소개하고자 한다.

 

그림과 같이 root가 아닌 임의 노드를 삭제하고 싶다면?

 

 

Solution 1. 카운팅

 

우선순위 큐의 요소에 대한 chk 배열을 만들어 삭제된 요소에 대해 카운팅을 하고, poll할 때 chk 배열의 값을 확인하는 방법이다. 위 그림에서 7 요소를 삭제하고 싶다면 chk[7]++ 이런 식으로 카운팅을 하고, poll할 때 chk배열의 값을 확인하여 1 이상이면 삭제된 것으로 간주한다. 하지만 이러한 방법은 우선순위 큐의 요소의 값이 충분히 작다는 것이 보장되어야 한다. 값의 범위 만큼 chk배열의 size가 결정되기 때문이다. 만약 일반적인 상황에서 봤을 때, 32bit Integer의 type의 경우 2^32의 size를 갖는 배열이 필요하므로 낭패를 보게된다.

 

 

Solution 2. 삭제 요소를 저장하는 별도의 자료구조 활용

 

우선순위 큐의 요소를 삭제할 때 마다 해당 요소를 별도의 자료구조에 저장하는 방법이다. 위 그림에서 7, 4, 1을 삭제하고 싶다면, 별도의 리스트나 배열을 활용해 삭제된 요소를 따로 기록해두는 것이다. 즉 삭제 요청이 들어올 때마다 바로 삭제 처리하는 것이 아닌, 필요할 때 삭제하는 것으로 미룬다는 점에서 Lazy하다. Solution 1보단 현실적인 방법이겠다만, 이 방법 역시 해당 요소가 우선순위 큐에서 삭제되었는지 확인하기 위해 순회할 때 O(N^2)의 성능을 보이므로 좋아보이는 방법은 아니다.

 

 

Solution 3. 삭제 요소를 저장하는 별도의 "우선순위 큐" 활용

 

우선순위 큐의 요소를 삭제할 때 마다 해당 요소와 weight 모두 우선순위 큐에 저장하는 방법이다. 그렇다면 삭제된 노드를 확인하는 과정에서 weight값도 함께 비교하여 O(logN)의 성능으로 처리할 수 있게된다. 삭제된 요소를 저장하는 우선순위 큐를 poll해서 요소를 계속해서 비교하되, 최대 힙 우선순위 큐에선 기준 노드의 weight보다 작을 경우 순회를 멈추어도 된다. 위 그림에서 7이 루트에 있다고 가정해보자. 그렇다면 삭제된 요소를 저장하는 우선순위 큐에서 루트노드의 weight가 7보다 작다면 적어도 7은 삭제 리스트에 존재하지 않는다는 의미가 된다.

 

해당 노드가 삭제되었는지 확인하기 위해서 삭제된 요소를 저장하는 우선순위 큐의 루트노드만 봐도 괜찮을 것이라 생각할 수 있지만, 기존의 우선순위 큐에 존재하지 않는 요소의 요청이 들어왔을 수도 있기에, 기준 노드의 weight와 비교하여 계속해서 poll하는 과정이 필요하다.