[자료구조] 트리 3. 힙 트리

힙 트리: 여러 개의 값들 중에서 가장 크거나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료 구조

힙은 최대 힙과 최소 힙으로 나눌 수 있으며, 모든 힙 트리는 아래의 두 성질을 만족해야 한다.

• 모양 성질: 완전 이진 트리의 모양을 나타내야 한다.
• 힙 성질: 최대 힙 또는 최소 힙의 특성을 갖는다.
  최대 힙의 특성: 각 노드에 저장된 값은 그 자식 노드에 저장된 값보다 크거나 같다.
  최소 힙의 특성: 각 노드에 저장된 값은 그 자식 노드에 저장된 값보다 작거나 같다.

최대 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

최소 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
이번에는 최대 힙을 가지고 다뤄보도록 하겠다!

---

최대 힙의 구현

최대 힙의 삽입은 단순히 트리에 항목을 삽입하는 형태가 아니다.
삽입이 이루어진 후에도 힙 성질을 만족해야 하기 때문에, 새로 삽입된 노드를 부모 노드들과 비교해서 자신의 알맞은 자리에 위치할 수 있도록 노드의 이동이 필요하다. 이를 업힙이라고 부른다. (최소 힙에서는 다운힙) 이 과정에서 O(log n)의 시간 복잡도가 소요된다.
최대 힙의 삭제는 어떻게 될까? 단순히 꺼내기만 하면 완전 이진 트리가 아니다. 삭제 연산에서도 힙 성질을 만족할 수 있도록 연산이 이루어져야 한다.
즉 루트 노드를 삭제하고, 가장 마지막 노드를 루트 노드로 올린 후 루트 노드를 자식 노드들과 비교하여 자신의 자리에 맞게 이동시켜주면 된다.

class MaxHeap: # 배열로 구현한 최대힙
    def __init__(self):
        self.heap = []
        self.heap.append(0) # 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 = '힙 트리: '):
        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]
            last = self.heap[self.size()]
            while child <= self.size():
                if child < self.size() and self.Left(parent) < self.Right(parent):
                    child += 1
                    # left보다 right가 더 클 경우 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

---

힙 트리의 응용) 배열로 구현한 최소 힙

class MinHeap: # 배열로 구현한 최소힙
    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 = '힙 트리: '):
        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]
            last = self.heap[self.size()]
            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

 

힙 트리의 응용) 허프만 코드

영어 단어들을 공부하다보면 알파벳 ‘z’에 비해서는 알파벳 ‘a’나 ‘e’가 더 빈번히 나오는 모습을 볼 수 있다. 이렇게 데이터의 빈도에 따라 가중치를 책정하여 압축하는 방식을 허프만 압축이라고 부른다.

import Heap

def make_tree(freq):
    heap = Heap.MinHeap() # 최소 힙을 이용한다.
    for i in freq:
        heap.insert(i)

    for i in range(1, len(freq)):
        e1 = heap.delete()
        e2 = heap.delete()
        heap.insert(e1 + e2)
        print(" (%d+%d)" % (e1, e2))


label = ['E', 'T', 'N', 'I', 'S']
freq = [15, 12, 8, 6, 4]
make_tree(freq)

 

 

작성일자: 2023-03-13