항해99 Weekly I learned 4주차 <알고리즘 편> <힙(Heap)>

힙(Heap)

: 힙은 힙의 특성을 만족하는 거의 완전한 트리(Almost Complete Tree)인 특수한 트리 기반의 자료구조다.

힙(heap)의 종류로는 최소힙과 최대힙으로 나눌 수 있다.

힙(Heap)은 그래프나 트리와는 전혀 관계 없어 보이는 독특한 이름과 달리, 트리 기반의 자료구조다. 우선순위 큐를 사용할때 매번 활동했던 heapq 모듈이 바로 힙으로 구현되어 있으며, 그중에서도 파이썬에는 최소 힙만이 구현되어있다.

최소힙은 부모가 항상 자식보다 작기 때문에 루트(root)가 결국 가장 작은 값을 갖게 되며, 우선순위 큐에서 가장 작은 값을 추출하는 것은 매번 힙의 루트를 가져오는 형태로 구현된다. 기반 구현을 살펴보면, 우선순위 큐 ADT(추상 자료형)는 주로 힙으로 구현되고, 힙은 주로 배열로 구현한다. 따라서 우선순위 큐는 결국은 배열로 구현하는 셈이 된다.

여기서 오해하기 쉬운 특징 중 하나는 힙은 정렬된 구조가 아니라는 점이다. 최소 힙의 경우 부모 노드가 항상 작다는 조건만 있을 뿐, 서로 정렬되어 있지 않다. 예를 들어, 아래의 그림처럼 부모노드가 자식노드보다 작을 뿐 자식들끼리는 정렬이 되어있지 않을 수 있다는 뜻이다.

(최소)힙 연산

이제 실제로 이진 힙을 구현해보자. 파이썬의 heapq 모듈에서 지원하는 최소 힙 연산을 여기서는 파이썬의 리스트만으로 동일하게 구현해보자. 먼저 이진 힙을 구협하기 위한 클래스 정의부터 진행해보자.

class BinaryHeap(object):
    def __init__(self):
        self.items = [None]
        
    def __len__(self):
        return len(self.items) - 1

클래스의 뼈대를 만들고, __len__() 메소드를 정의했다. __len__ 처럼 밑줄( _ ) 2개로 둘러싸인 함수는 파이썬의 매직 메소드로 여러 가지 내부기능이 동작되는 데 사용된다. 예를 들어 len(a)를 하게 되면, 내부적으로 a.__len__()을 호출하여 이 결과를 리턴하게 된다. 여기서도 len()으로 호출하면 마지막 요소의 인덱스를 가져오기 위해 실제 길이보다 하나 더 작은 값을 가져오도록, __len__() 함수에서 실제 len()의 결과와는 조금 다른 형태로 구현해뒀다. 아울러 0번 인덱스는 사용하지 않기 위해 None을 미리 설정해뒀다.

최소힙) 삽입(Insert)

힙에 요소를 삽입하기 위해서는 업힙(Up-Heap) 연산을 수행해야 한다. 일반적으로 업힙 연산은 percolate_up()이라는 함수로 정의한다. 힙에 요소를 삽입하는 과정을 살펴봅시다.

1. 요소를 가장 하위 레벨의 최대한 오른쪽으로 삽입한다.( 배열로 표현할 경우 가장 마지막에 삽입한다)
2. 부모 값과 비교해 값이 더 작은 경우 위치를 변경한다.
3. 계속해서 부모 값과 비교해 위치를 변경한다.(가장 작은 값일 경우 루트까지 올라간다.)

이 과정을 코드로 구현해보면 다음과 같다.

def _percolate_up(self):
    i = len(self)
    parent = i // 2
    while parent >= 0:
        if self.items[i] < self.items[parent]:
            self.items[parent], self.items[i] = \
                self.items[i], self.items[parent]
        i = parent
        parent = i // 2


def insert(self, k):
    self.items.append(k)
    self._percolate_up()

삽입 자체는 insert() 함수를 호출해 실행된다. items인 1을 삽입하고, 삽입한 1을 부모노드와 비교해가면서 위로 올라가는 부분이 percolate_up() 함수 부분이다. 1은 결국 부모노드와 비교해가면서 최상위 레벨로 안착하게 된다. 시간 복잡도는 O(log n)이 된다.

최소힙) 추출(extract)

추출 자체는 매우 간단하다. 루트를 추출하면 된다. 그렇다면 시간 복잡도는 O(1)이라고 생각할 수 있겠지만, 추출 이후에 다시 힙의 특성을 유지하는 작업이 필요하기 때문에 시간 복잡도는 O(log n)이다.

위에 그림에서 바와 같이 추출의 수순을 설명할 수 있다.
1. 먼저 1을 다른 변수에 넣어준다.
2. 1이 있는 자리에 배열 맨 끝에 있는 6을 넣어준다.
3. pop()으로 맨끝에 있던 6을 꺼내서 버린다.
4. 이제 6을 percolate_down으로 정렬을 해준다.
5. 1이 들어있는 변수를 리턴해준다.

이와 같은 추출 코드는 아래와 같이 작성할 수 있다.

def _percolate_down(self, idx):
    left = idx * 2
    right = idx * 2 + 1
    smallest = idx
    
    if left <= len(self) and self.items[left] < self.items[smallest]:
        smallest = left
    if right <= len(self) and self.items[right] < self.items[smallest]:
        smallest = right
    
    if smallest != idx:
        self.items[idx], self.items[smallest] = \
            self.items[smallest], self.items[idx]
        self._percolate_down(smallest)
        
def extract(self):
    extracted = self.items[1]
    self.items[1] = self.items[len(self)]
    self.items.pop()
    self._percolate_down(1)
    return extracted

이런 식으로 최소힙을 구현할 수가 있다. 그리고 최소힙과 반대인 최대힙의 경우 최소힙과 반대로 아래처럼 구현을 할 수 있다.

class BinaryMaxHeap:
    def __init__(self):
        # 계산 편의를 위해 0이 아닌 1번째 인덱스부터 사용한다.
        self.items = [None]

    def __len__(self):
        # len() 연산을 가능하게 하는 매직 메서드 덮어쓰기(Override)
        return len(self.items) - 1

    def _percolate_up(self):
        # percolate : 스며들다.
        cur = len(self)
        # left 라면 2*cur, right 라면 2*cur + 1 이므로
        # parent는 항상 cur // 2
        parent = cur // 2

        while parent > 0:
            if self.items[cur] > self.items[parent]:
                self.items[cur], self.items[parent] = \
                    self.items[parent], self.items[cur]

            cur = parent
            parent = cur // 2

    def _percolate_down(self, cur):
        biggest = cur
        left = 2 * cur
        right = 2 * cur + 1

        if left <= len(self) and self.items[left] > self.items[biggest]:
            biggest = left

        if right <= len(self) and self.items[right] > self.items[biggest]:
            biggest = right

        if biggest != cur:
            self.items[cur], self.items[biggest] = self.items[biggest], self.items[cur]
            self._percolate_down(biggest)

    def insert(self, k):
        self.items.append(k)
        self._percolate_up()

    def extract(self):
        if len(self) < 1:
            return None

        root = self.items[1]
        self.items[1] = self.items[-1]
        self.items.pop()
        self._percolate_down(1)

        return root

최대힙의 경우, insert와 extract 부분이 같지만 percolate 부분이 달라짐으로 인해 최대힙과 최소힙이 갈리게 된다.