Python으로 힙(Heap) 구현하기

힙은 우선 순위가 존재하는 데이터를 처리하기 위한 큐 구조 중 하나이다. 우선순위가 높은 자료부터 꺼내서 빠르게 처리하기 위해 만들어졌다.

 

우선 순위가 있는 데이터의 예로는 대표적으로 OS에서 프로세스의 처리 과정이 있다. 우리가 사용하는 Windows, Linux 등 모든 OS에서는 프로세스의 우선순위를 부여할 수 있는 기능이 존재한다. 만약 CPU를 많이 차지하고, 처리하는데에 오래 걸리는 작업이 있다면 우선순위를 낮춰서 CPU가 한가할 때 작업을 처리할 수 있도록 한다.

 

 

우리가 힙이라고 부를 수 있는 구조의 조건으로는 두 가지가 있다.

 

• 1) 노드(node)들이 완전 이진 트리 구조를 가져야 한다.
• 2) 노드들이 우선순위에 따라 오름/내림차순으로 배열되어 있어야 한다.

1)의 완전 이진 트리 구조는 다음과 같이 각 노드가 최대 두 개의 자식노드를 가지고, 맨 아래 레벨에 대해 왼쪽에서부터 채워지는 트리 구조를 의미한다.

완전 이진 트리의 구조

2)의 이야기는 부모 노드의 값이 자식 노드의 값보다 항상 크거나(작거나) 같아야 한다는 의미이다. 이때 맨 위의 루트에 가장 큰 값이 저장되는 힙 구조를 최대 힙 (Max heap), 가장 작은 값이 저장되는 힙 구조를 최소 힙(Min heap)이라고 한다.

 

파이썬에서는 heapq 모듈을 통해 힙의 구현을 내장모듈로서 지원한다. 그러나, 이번 글에서는 힙의 알고리즘을 파악하기 위해 직접 구현해본다. 최대 힙과 최소 힙은 알고리즘이 매우 유사하기 때문에, 최대 힙만 구현해보도록 하자.

 

힙의 자료에 원소를 삽입, 삭제하거나, 혹은 파이썬의 list를 완전 이진 트리로 변환하는 과정에는 Percolate Up & Down이 사용된다. 간단하게 힙에 원소를 삽입하는 과정의 코드를 짜면서 알아보도록 하자.

 

힙에 원소를 삽입하는 과정을 그림으로 표현하면 다음과 같다.

 

8이라는 값을 힙에 넣게 될 경우

8이라는 값을 힙에 삽입할 경우, 맨 아래 레벨의 노드에 8이 들어가게 되면 정렬이 깨지게 된다. 따라서, 부모 노드와의 크기 비교를 통해 부모 노드보다 크기가 작게 되는 위치까지 8을 위로 올려보내게 된다. 이러한 알고리즘을 Percolate Up이라고 한다.

 

Percolate Up이 완료된 힙

 

다음은 이를 파이썬 코드로 표현해 보자. 힙에 원소 x를 넣는 함수 insert(self, x)와 Percolate Up을 실행하는 재귀적인 클래수 내부 함수 __percolateup(self, i)를 구현해보았다.

 

    def insert(self, x):
        self.__hp.append(x)
        self.__percolateup(len(self.__hp) - 1)

    def __percolateup(self, i):
        parent = (i - 1) // 2
        if i > 0 and self.__hp[i] > self.__hp[parent]:
            self.__hp[i], self.__hp[parent] = self.__hp[parent], self.__hp[i]
            self.__percolateup(parent)
            # 재귀적인 구조

 

이런 식으로 힙에 원소를 삽입할 수 있게 된다.

 

반대로 최대 힙에서 우선순위가 가장 큰 원소를 삭제하는 경우, 맨 위의 루트를 바로 삭제해버리면 트리의 구조가 깨지기 때문에 다음과 같은 방법으로 삭제를 진행한다.

1. 우선순위가 가장 큰 1 번째 원소를 삭제하고, n 번째 원소를 루트 자리에 올려놓는다.
2. 루트 노드에 대해 부모보다 자식노드의 값이 더 클 것이기 때문에, Percolate Down 방식으로 루트에 있는 값을 다시 아래로 내려준다.

이러한 방식을 통해 원소의 삭제도 구현할 수 있다. 자세한 코드는 아래 전체 코드에 적어놓았다.

 

마찬가지로 일반 list 형태의 자료에 대해 heap과 같이 우선순위를 부여하는 코드도 작성할 수 있다. 임의의 노드에 대하여 모든 원소가 정렬될 때까지 Percolate Down을 수행해주면 된다.

 

이러한 작업들을 정리해서 코드로 구현해보자.

class Heap:
    def __init__(self, *args):      # *args : 여러 개의 인자를 tuple 형태로 받음
        if lens(args) != 0:
            self.__hp = arg[0]      # Heap으로 표현되는 리스트 : hq = list()
        else:
            self.__hp = []

    # 힙에 원소 x를 삽입하는 함수
    def insert(self, x):
        self.__hp.append(x)
        self.__percolateup(len(self.__hp) - 1)
    
    # Percolate Up을 실행하는 함수
    def __percolateup(self, i):
        parent = (i - 1) // 2
        if i > 0 and self.__hp[i] > self.__hp[parent]:
            self.__hp[i], self.__hp[parent] = self.__hp[parent], self.__hp[i]
            self.__percolateup(parent)
            # 재귀적인 구조

    # 힙에서 가장 큰 원소를 삭제하고, 이를 반환하는 함수
    def deletemax(self):
        if len(__hp) != 0:
            max = self__hp[0]
            self.__hp[0] = self.__hp.pop()
            self.__percolatedown(0)         # 맨 위로 옮겨진 원소를 Percolate Down
            return max
        else:
            return None
    
    # Percolate Down을 실행하는 함수
    def __percolatedown(self, i):
        left = 2 * i + 1        # 부모 노드 기준 왼쪽 노드
        right = 2 * i + 2       # 부모 노드 기준 오른쪽 노드
        child = left            # Percolate Down 실행할 방향 : child
        if left <= len(self.__hp) - 1:
            if right <= len(self.__hp) - 1 and self.__hp[left] < self.__hp[right]:
                child = right 
            if self.__hp[i] < self.__hp[child]:
                self.__hp[i], self.__hp[child] = self.__hp[child], self.__hp[i]
                self.__percolatedown(child)
    
    # 힙 만들기
    def buildheap(self):
        for i in range((len(self.__hp)-2) // 2, -1, -1): # 맨 끝 노드의 부모노드로부터 역순으로 루트까지
            self.__percolatedown(i)

 

 

 

파이썬에는 heapq 모듈이 있고, 이 모듈을 통해 위와 같은 구현 없이 최소 힙 기능을 바로 이용할 수 있다. 그러나 위와 같은 방식으로 구현을 해보는 것은 파이썬의 기능들에 대한 이해도를 높여주기 때문에, 꼭 한번씩 해보는 것을 추천한다.