Binary Heap

priority queue는 큐와 동일하게 동작하는 듯 보이는 비슷한 자료 구조이다. 뒤쪽으로 원소를 삽입하고 앞쪽으로 꺼낸다. 하지만 각 원소는 내부적으로 논리적인 우선순위 값을 가지고 있어서 큐 내부에서는 높은 우선순위를 갖는 원소가 앞쪽으로 오게 된다. 즉, 큐에서 꺼낼 때는 앞에서부터 꺼내게 되는데, 이 순서가 큐 내부에서의 우선순위 순과 일치하게 되는 것이다. 따라서 priority queue에 새 원소를 추가하면 때에 따라서는 이 원소가 곧장 큐의 맨 위로 이동할 수도 있는 것이다.

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

간단히 생각해보면 priority queue는 리스트와 정렬함수를 쓰면 간단히 구현할 수 있을 것 같다. 하지만 리스트에 무언가를 삽입하는 것은 \(O(n)\)의 성능을 내고, 리스트를 정렬하는 것은 \(O(n{log}n)\)의 성능을 낸다. 하지만 실제로는 이보다 더 좋은 성능을 만들 수 있다. 바로 바이너리 힙(Binary Heap)이라는 자료 구조를 사용하는 것이다.

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

여기서는 예제로 minHeap을 한 번 구현해보도록 하자. 이 클래스는 다음과 같은 기능을 제공해야 한다.

  • BinaryHeap() : 새로운 바이너리 힙 객체를 생성. 새 객체는 비어있는 상태이다.
  • insert(k) : k 값을 추가
  • findMin() : 최소값을 찾아서 리턴. 단 찾은 값은 내부에 남겨둔다.
  • delMin() : 최소값을 찾아서 리턴. 찾은 최소값은 힙에서 삭제된다.
  • isEmpty() : 비어있는 힙인지를 알려준다.
  • size() : 힙의 크기(내부의 아이템 수)를 리턴한다.
  • buildHeap(list) : 주어진 리스트를 사용해서 새 힙을 생성한다.

일단 클래스의 코드는 다음과 같다.

class BinHeap():

    def __init__(self):
        self.heapList = [0, ]
        self.currentSize = 0

    def percUp(self, i):
        while i > 0:
            if self.heapList[i] < self.heapList[i // 2]:
                self.heapList[i], self.heapList[i // 2] =\
                    self.heapList[i // 2], self.heapList[i]
            i = i // 2

    def insert(self, k):
        self.heapList.append(k)
        self.currentSize = self.currentSize + 1
        self.percUp(self.currentSize)

    def minChild(self, i):
        if i * 2 + 1 > self.currentSize:
            return i * 2
        else:
            if self.heapList[i * 2] < self.heapList[i * 2 + 1]:
                return i * 2
            else:
                return i * 2 + 1

    def delMin(self):
        retVal = self.heapList[1]
        self.heapList[1] = self.heapList[self.currentSize]
        self.currentSize = self.currentSize - 1
        self.heapList.pop()
        self.percDown(1)
        return retVal

    @property
    def isEmpty(self):
        return self.getHeap() == []

    @property
    def size(self):
        return self.currentSize

    def getHeap(self):
        return self.heapList[1:]

    def findMin(self):
        if self.isEmpty:
            return None
        else:
            return self.heapList[1]

    def percDown(self, i):
        while (i * 2) <= self.currentSize:
            mc = self.minChild(i)
            if self.heapList[i] > self.heapList[mc]:
                self.heapList[i], self.heapList[mc] = \
                    self.heapList[mc], self.heapList[i]
            i = mc

    def buildHeap(self, alist):
        i = len(alist) // 2
        self.currentSize = len(alist)
        self.heapList = [0] + alist[:]
        while (i > 0):
            self.percDown(i)
            i -= 1

동작 방식은 다음과 같다.

  1. 바이너리 힙은 i 번째 원소에 대해 그 자식 노드를 각각 i2, i2+1 번째 노드로 정의한다. 이 구조 때문에 1개의 리스트에 원소를 저장하면서 트리 구조를 유지하는 것이 가능하다.
  2. 0번째 원소는 임의의 값으로 채워놓는다. (0 * 2 = 0 이니, 이 지점은 트리구조 상의특이점이므로 무시해야 한다.)
  3. 원소를 추가하면 리스트의 맨 뒤에 붙게 된다. 여기 까지는 큐와 동일한데, 원소가 추가된 뒤에는 이 원소가 자신의 부모노드보다 작으면 부모노드와 위치를 바꾸면서 큐의 앞쪽으로 이동해 나간다.
  4. 앞에서 최소값을 빼기 시작하면, 트리 구조 유지를 위해서 채워넣는 작업이 필요한데…
    1. 여기서 만약 루트의 자식 노드 중 하나를 이동시키려면 비용이 많이 든다.
    2. 또한, 3에서 추가된 원소는 자신의 직계 트리만 비교하므로, 두, 세번째로 작은 값이 추가되었을 때 반드시 제 위치로 가 있게 된다는 보장이 없다.
    3. 따라서 맨 뒤의 값을 맨 앞으로 옮긴다음, 이 값이 자신의 위치를 찾아갈 수 있도록 한다.
  5. 맨 뒤의 값을 루트 위치로 옮긴다음, 그 두 자식과 비교하여 작은 자식과 위치를 교환한다. 물론, 그 두 사직 노드는 자신보다 큰 값이어야 한다.

이 방식을 통해서 삽입될 때, 그리고 추출될 때 바이너리 힙은 부분적인 정렬을 하게 된다. 따라서 항상 정렬된 리스트의 형태를 유지하지는 않지만, 빠져나오는 값은 늘 최소값이 됨을 보장하게 된다.