힙

힙

Heap

힙의 사전적 의미는 더미라고 한다. 힙은 완전이진트리 기반의 자료구조이다. 최대값, 혹은 최소값을 root에 올리고 이를 바탕으로 빠르게 값을 찾는 트리이다. 힙의 특징이라면 느슨한 정렬을 유지한다는 점이 있다.

Heap의 구현

힙은 루트가 최대값인 Max, 최소값인 Min 두가지 종류가 있다. 파이썬의 경우 heapq를 통해 min Heap은 이미 구현되어있다. 따라서 Max Heap을 구현하도록 하겠다. 힙은 리스트를 통해 구현되며, 트리의 기본 성질을 이용한다.

class MaxHeap:
    def __init__(self):
        self.heap = []
        self.heap.append(0)

    def size(self):
        return len(self.heap) - 1

    def isEmpty(self):
        return self.size() == 0

    def parent(self, i):
        return self.heap[i // 2]

    def left(self, i):
        return self.heap[i * 2]

    def right(self, i):
        return self.heap[i * 2 + 1]

    def display(self, msg = 'Max Heap : '):
        print(msg, self.heap[1:])

    def insert(self, n):
        self.heap.append(n)
        i = self.size()
        while i != 1 and n > self.parent(i):
            self.heap[i] = self.parent(i)
            i = i // 2
        self.heap[i] = n

    def delete(self):
        parent = 1
        child = 2
        if not self.isEmpty():
            hroot = self.heap[1] # set parent as hroot
            last = self.heap[self.size()] # set last node as last
            while child <= self.size():
                if child < self.size() and self.left(parent) < self.right(parent):
                    child += 1
                if last >= self.heap[child]:
                    break
                self.heap[parent] = self.heap[child]
                parent = child
                child *= 2

            self.heap[parent] = last
            self.heap.pop(-1)
            return hroot

특이하게 볼 연산은 insert와 delete이다.

insert

    def insert(self, n):
        self.heap.append(n)
        i = self.size()
        while i != 1 and n > self.parent(i):
            self.heap[i] = self.parent(i)
            i = i // 2
        self.heap[i] = n

삽입은 여느 트리와 마찬가지로 말단노드에 삽입을 한다. 그리고 자신의 부모노드와 비교하며, 만약 자식이 부모보다 크다면 계속 교환해 나가면서 트리를 구성한다.

delete

def delete(self):
        parent = 1
        child = 2
        if not self.isEmpty():
            hroot = self.heap[1] # set parent as hroot
            last = self.heap[self.size()] # set last node as last
            while child <= self.size():
                if child < self.size() and self.left(parent) < self.right(parent):
                    child += 1
                if last >= self.heap[child]:
                    break
                self.heap[parent] = self.heap[child]
                parent = child
                child *= 2

            self.heap[parent] = last
            self.heap.pop(-1)
            return hroot

삭제의 경우 조금 더 복잡하다. 삭제의 경우 우선 루트노드만이 삭제가 가능하다. 그 후, 왼쪽자식과 오른쪽 자식을 비교하며, 더 큰 자식과 부모노드를 계속 바꿔준다. 만약 더 이상 자식이 없는 위치에 도달한다면 마지막 값을 지우면 삭제 연산의 완료이다.

허프만 코드

힙의 활용법은 힙정렬도 있지만, 우선 허프만 코드에 대해 알아보도록 하겠다.

허프만 코드란?

영어를 보다보면 알파벳 e는 많이 나오는데, z나 x같은 알파벳은 거의 안나온다는걸 알 수 있다. 이를 통해, 우리는 이진트리를 이용하여 어떤 문서에 어떤 알파벳이 많이 있고 이를 이용해 압축을 할 수 있다.

우리가 평소 자주 사용하는 아스키 코드를 사용하면, 물론 표현은 가능하지만, 압축 측면에서 길이가 모두 고정되어있기 때문에 비효율이 발생한다. 따라서 가변코드를 사용하여 빈도가 많은 문자는 적은 코드를, 빈도가 적은 문자는 긴 코드를 주도록 한다.

예시

AAABBBBCCCDDEEEEEFFFFFFF 라는 문자열을 압축한다고 하자
고정길이를 쓰면, 총 6개의 문자이기 때문이 2^2 < 6 < 2^3승인 3bit 2진수로 표현해야한다
하지만 허프만코드 가변길이를 쓰면, 더 간단하게 표현 할 수 있다.

그렇다면 어떻게 허프만 코드를 쓸 수 있는걸까?

허프만 코드 생성

sinte 라는 문자가 4 6 8 12 15 번 사용된다고 하자.

1. 우선, 가장 작은 두 빈도수를 각각 좌측 자식, 우측자식으로 설정한다.

2. 두 빈도수의 합을 부모노드로 설정한다.

3. 위의 과정을 반복하여 이진트리를 계속 구성한다.

4. 구성이 완료되면, 왼족은 1, 오른쪽은 0으로 설정하고 결정트리에서 그랬던것처럼 찾아내려가도록 한다.

허프만 코드 구현

from queue import PriorityQueue

PQ = PriorityQueue()


class HuffNode:
    def __init__(self, symbol, freq):
        self.symbol = symbol
        self.freq = freq
        self.left = None
        self.right = None


    def preorder(self):
        print(self.freq, end=" ")

        if (self.left is not None):
            self.left.preorder()
        if (self.right is not None):
            self.right.preorder()


    def inorder(self):
        if (self.left is not None):
            self.left.inorder()

        print(self.freq, end=" ")
        if (self.right is not None):
            self.right.inorder()


def huffman(n, PQ):
    for _ in range(n - 1):
        p = PQ.get()[1]
        q = PQ.get()[1]
        r = HuffNode(' ', p.freq + q.freq)
        r.left = p
        r.right = q
        PQ.put((r.freq, r))
    return PQ.get()[1]


codes = ['E', 'T', 'N', 'I', 'S']
freqs = [15, 12, 8, 6, 4]

for i in range(len(codes)):
    node = HuffNode(codes[i], freqs[i])
    PQ.put((node.freq, node))

root = huffman(len(codes), PQ)

print("Preorder:", end=" ")
root.preorder()
print("\nInorder:", end=" ")
root.inorder()
print()

교재에 있는 minHeap을 이용해서 구현해보려 했는데, 잘 안되었다. 결국 오랜 스승, 유튜브의 주니온 TV의 도움을 받아 해결하였다. 풀고나니 참 간단하다.

1. 코드와 빈도수를 담은 노드를 생성한다.

2. 각 노드를 우선순위큐에 집어넣는다. 이 우선순위 큐에서는 노드의 빈도수와 노드정보를 담고 있다.

3. 노드의 합을 새로운 노드 r로 만들고, r의 좌 우 값을 기존의 노드값으로 넣는다. 이떄, r노드는 코드가 없다

4. 완성된 노드를 트리라 생각하면 BST를 이용하여 말단노드에서 코드를 작성하게 할 수 있다.

힙 정렬

나중에 합시다