우선순위 큐 혹은 최소/최대힙

우선순위 큐 (priority queue)는 큐와 비슷하게 뒤쪽으로 원소를 삽입하고 앞쪽으로 꺼낼 수 있는 자료 구조이다. 하지만 각 원소는 내부적으로 논리적인 우선순위 값을 가지고 있고, 따라서 선입선출(FIFO)의 규칙에 의해서 나오는 것이 아니라, 큐 내부에서는 높은 우선순위를 갖는 원소가 앞쪽으로 오게 된다. 즉, 큐와 마찬가지로 원소를 꺼낼 때는 앞에서부터 꺼내게 되는데, 이 순서가 큐 내부에서의 우선순위 순과 일치하게 되는 것이다. 일종의 자동으로 정렬되는 큐라고 생각하면 된다. 언어나 알고리듬 책에 따라서는 이를 최소/최대힙(min/max heap) 혹은 힙큐(heap queue)라고 부르기도 한다.

priority queue는 나중에 보게 될 그래프 알고리듬에서 유용하게 쓰일 수 있으니 잠깐 살펴보고 진행하고자 한다.

간단히 생각해보면 priority queue는 리스트와 정렬함수를 쓰면 간단히 구현할 수 있을 것 같다. 하지만 리스트에 무언가를 삽입하는 것은 (리스트의 맨 뒤자리를 탐색해야 하므로) O_{(n)}의 성능을 내고, 리스트를 정렬하는 것은 통상적인 좋은 정렬 알고리듬들이 그러하듯  O_{(n{log}_n)}의 성능을 낸다.

하지만 실제로는 이보다 더 좋은 성능을 만들 수 있다. 바로 바이너리 힙(Binary Heap)이라는 자료 구조를 사용하는 것이다.

바이너리 힙은 매우 흥미로운 주제 중 하나인데, 트리형태의 자료를 단순히 하나의 리스트로만 구현하기 때문이다. 바이너리 힙은 두 가지 유형을 갖는데, 최소 값이 앞으로 오는 minHeap의 형태와 반대로 최대값이 앞으로 오는 maxHeap의 형태가 있다. 둘의 차이는 작은 값이 우선하느냐 큰 값이 우선하느냐의 차이만 있고 구현 방식은 동일하다.

 

이론적 배경

바이너리 힙은 바이너리 트리를 하나의 리스트 혹은 배열로 구현한 것이다.

                 0
               /    \
              1      2
            /   \   /  \
           3    4   5   6
           ,,,,,,,,,,,,,,

리스트의 맨 첫 인덱스에 위치하는 원소가 트리의 루트가 되고, 그 다음 두 개의 자식에 각각의 인덱스를 부여한다.  이 때 각 인덱스와 그 자식노드들의 인덱스를 비교해보면, 원래 인덱스가 i 일 때, 다음 관계가 성립하는 것을 알 수 있다.

  • 현재 노드의 인덱스: i
  • 부모노드의 인덱스 : (i - 1) // 2
  • 왼쪽 자식 노드의 인덱스 : i * 2 + 1
  • 오른쪽 자식 노드의 인덱스: i * 2 + 2

이 구조는 전체적인 틀이 이미 짜여져 있는 모양이며, 왼쪽 위 노드부터 차곡차곡 노드를 채워나가는 구조를 하고 있다. 따라서 새로운 값이 삽입될 때에는 기본적으로 리스트의 맨 뒤에 값을 추가한다.

하지만 가장 우선순위가 높은 값이 큐의 출구 앞에 있어야 하고, 이는 루트 노드에 해당한다. 따라서 삽입의 동작은 다음과 같은 절차를 거쳐야 한다.

  1. 삽입되는 값은 최초에 리스트의 맨 뒤에 추가된다.
  2. 삽입된 값은 자신의 부모노드와 비교하여 더 높은 우선순위를 가지는 비교한다.
  3. 만약 부모노드가 존재하고, 그 우선순위가 자기보다 낮다면 부모노드와 자신의 위치를 교환한다.
  4. 3의 과정을 가능할 때까지 계속 반복한다.

그렇게하면 마치 버블정렬의 모양처럼 가장 높은 우선순위의 값이 위쪽으로 떠오르는 모양이 될 것이다. 물론 현재 루트 노드가 최우선 노드라면 그 위치가 변경되지는 않겠지만, “새로 추가된 값은 가능한 가장 앞쪽으로 이동”한 상태가 될 것이다.

노드 추가

이 과정까지를 코드로 구현해보면 다음과 같다.

class BinHeap:
  def __init__(self):
    self.data = []

  def _move_up_from(self, i):
    '''인덱스 i에 있는 노드값을 가능한 위쪽으로 이동시킨다.'''
    while i > 0:
      p = (i - 1) // 2
      if self.data[i] < self.data[p]:
        self.data[i], self.data[p], i = self.data[p], self.data[i], p
  
  def insert(self, obj):
    self.data.append(obj)
    self._move_up_from(len(self.data) - 1)

특정 위치에서 그 부모노드의 인덱스를 계산할 수 있고, 값을 비교해서 교환하는 작업을 반복하면 되는 것이기 때문에 이 과정은 그리 어렵지 않다.

그렇다면 노드값을 빼내는 것은 어떻게 구현할까?

노드 제거

우선순위 큐에서 값을 빼낼 때, 빼내야 하는 값이 맨 왼쪽(맨 앞)에 있는 노드임은 자명하다. 삽입된 노드들 중에서 가장 높은 우선순위에 해당하는 노드가 가장 앞으로 오게 될 것이기 때문이다. 그렇다면 노드를 제거한 이후의 동작은 어떠해야 할까?

  1. 먼저 각 노드의 인덱스를 생각해보면, 이진트리 모양의 위치에서 인덱스는 노드의 위치를 고정적으로 가리킬 뿐만 아니라, 인덱스 값을 통해서 부모/자식 간의 관계를 파악한다. 따라서 인덱스를 일괄적으로 앞/뒤로 미는 연산은 여기에 사용될 수 없다.
  2. 제거된 루트노드는 빈자리가 되고, 이 빈자리를 채울 두 후보는 바로 해당 노드의 좌/우 자식 노드이다. 이 때에도 서브 트리가 통째로 이동하는 것은 불가능하므로 둘 중 하나가 위로 올라오고 다시 그 서브 노드에서 빈자리를 메꾸는 동작을 취해야 한다.
  3. 하지만 2의 동작을 “빈 자리”를 사용하는 것은 비효율적일 수 있는데 왜냐하면 바이너리 힙에서는 구조 상 리스트 중간에 None 값이 올 수 없기 때문에 어쨌든 최종단까지 교체 작업을 반복해야 하기 때문이다.
  4. 따라서 보다 나은 방법은 맨 뒤에 있는 요소를 루트 위치로 옮긴 후, 3의 동작을 반복한다.

따라서 특정 노드 위치로부터 이 값이 낮은 우선순위를 가지고 있을 때 어디로 내려가야 할지를 판단해서 정리하는 메소드가 필요해보인다.  이 구현은 다음과 같은 알고리듬을 따른다.

  1. i로부터 왼쪽자식의 인덱스와 오른쪽 자식의 인덱스를 찾는다.
  2. 왼쪽 자식의 인덱스가 데이터리스트의 크기보다 크거나 같으면 자식이 존재하지 않는다. 이 때는 중단한다.
  3. 오른쪽 자식의 인덱스가 데이터리스트의 크기보다 크거나 같으면 왼쪽 자식만 존재한다. 이 때 왼쪽 자식이 i번째 요소보다 작다면 두 위치를 바꾼 후, 현재 인덱스를 왼쪽 자식의 인덱스로 바꾼다.
  4. 자식이 두 개 있는 경우, 두 자식 중 더 작은 자식과 현재 인덱스가 가리키는 노드를 비교한다. 자식 노드가 더 작다면 두 노드를 교환하고, 인덱스도 업데이트한다.
  5. 이 과정을 더 이상 계속할 수 없을 때까지 반복한다.

이를 이용하면 노드를 순차적으로 제거하는 코드를 작성할 수 있다.

def _move_down_from(self, i):
  l = len(self.data)
  while True:
    leftc, rightc = i * 2 + 1, i * 2 + 2
    if l <= leftc:
      ## 자식 노드가 존재하지 않음
      return
    elif l <= rightc:
      ## 왼쪽 자식 노드만 있음
      if self.data[i] > self.data[leftc]:
        self.data[i], self.data[leftc], i = self.data[leftc], self.data[i], leftc
      else:
        ## 그 자식노드가 자신보다 큼
        return
    else: ## 두 개 노드가 다 있음
      target = leftc if self.data[leftc] < self.data[rightc] else rightc
      if self.data[i] > self.data[target]:
        self.data[i], self.data[target], i = self.data[target], self.data[i], target
      else:
        return

def pop(self):
  result = self.data[0]
  if len(self.data) > 1:
    ## 맨 뒤 값을 루트로 옮긴다음, 아래로 내려보낸다.
    self.data[0] = self.data.pop()
    self._move_down_from(0)
  else:
    ## 1원소 리스트인 경우, 빈 리스트로 만든다.
    self.data.pop()
  return result
 

최종적으로 이렇게 만들어진 클래스를 이용해서 다음과 같이 힙정렬을 수행해 볼 수 있다. 힙 정렬은 최소힙을 사용해서 리스트의 원소를 순차적으로 힙에 부어넣고 차례로 빼어내어 정렬한다.

l = [5, 2, 9, 7, 3, 6, 8]
dq = BinHeap()
for i in l: dq.push(i)
sorted_l = [dq.pop() for _ in range(len(l))]
## [2,3,5,6,7,8,9]

정리

우선순위 큐 혹은 최대최소 힙은 원소의 추가/삭제가 빈번한 상황에서 항상 리스트 내의 최소값 혹은 최대값을 기준으로 값을 꺼내어 쓰는 경우에 유용하다. 특히 이러한 경우는 다익스트라 알고리듬이나 A-Star알고리듬과 같이 리스트의 초기 상태 이후에 원소가 추가되더라도 늘 최소값을 즉시 찾아내어야 하는 경우에 유리하게 사용할 수 있는 자료구조이다.

참고로 파이썬에서는 heapq라는 모듈에서 기본적으로 구현된 힙큐를 제공하고 있다.