<코딩테스트 Level1> 13일차 - 완전 이진 트리, 힙

📌 완전 이진 트리

이진 탐색 트리는 내가 어떤 데이터를 넣느냐에 따라 자유로운 형태를 지닌 반면, 힙 자료구조는 트리의 형태가 정해져 있다. 바로 완전 이진 트리라고 불리는 형태이다.

완전 이진 트리는 이진 트리 중 노드가 왼쪽부터 차례대로 채워져 있는 트리를 의미한다.

📌 완전 이진 트리 사용 이유

이전까지 배운 트리는 단순 이진 트리로 데이터를 어떻게 넣느냐에 따라 형태가 변화했다. 하지만 완전 이진 트리는 무조건 트리의 왼쪽부터 데이터를 채우기 때문에 데이터를 어떻게 넣는 지에 관게없이 동일한 구조를 갖는다.

따라서 지금까지 사용했던 링크드 리스트 방식의 구현이 아닌 배열을 사용한 코드 구현이 가능하다.

완전 이진 트리에 A - B - ... - F - G 순서로 데이터가 들어온다고 가정하자. 아래와 같은 트리가 만들어진다.

하지만 또 다른 방식으로 데이터가 들어오는 순서대로 배열의 1번 인덱스부터 하나씩 채워나간다면 어떨까 ❓

• A - B - C로 이어지는 1, 2, 3의 관계
• B - D - E로 이어지는 2, 4, 5의 관계
• C - F - G로 이어지는 3, 6, 7의 관계

트리를 한 줄 더 늘려서 살펴보자.

왼쪽 자식의 인덱스는 부모 노드 인덱스 x 2의 값을 가지고,
오른쪽 자식의 인덱스는 부모 노드 인덱스 x 2 + 1의 값을 가진다.

부모 노드의 인덱스는 자식 노드 인덱스를 2로 나눈 몫이 된다.

이런 특정으로 인해 링크드 리스트가 아닌 배열과 인덱스를 사용해 구현할 수 있다.

📌 힙

힙은 두 가지 종류가 존재한다.

1. 부모 노드가 항상 자식 노드보다 작은 완전 이진 트리 형태
2. 부모 노드가 항상 자식 노트보다 큰 완전 이진 트리 형태

이 때 부모 노드가 항상 자식 노드보다 작은 형태를 최소 합이라고 하고, 부모 노드가 항상 자식 노드보다 큰 형태를 최대 합이라고 한다.

이 중 최소 합, 즉 부모 노드가 트리 전체에서 가장 작은 값을 갖는 힙을 구현해보자.

📌 힙 선언

첫 단계는 힙을 선언해야 한다.
힙은 완전 탐색 트리이기 때문에 배열을 사용해 구현한다.

MAX_HEAP_SIZE = 101

class Heap:
    def __init__(self):
        self.arr = [None] * MAX_HEAP_SIZE
        self.heap_count = 0

📌 힙에 데이터 삽입

다음 단게는 힙에 데이터 삽입이다.

이진 탐색 트리는 왼쪽, 오른쪽 자식 값에 대한 조건이 존재했지만, 힙은 단순히 자식이 부모보다 크다라는 큐칙 하나만 지키면 된다.

데이터 삽입은 아래 과정을 거쳐 진행된다.

아래 트리에서 새로운 노드 2가 삽입된다고 가정보자.

완전 이진 트리이기 때문에, 왼쪽부터 자리를 채워야 하므로 6번 노드의 오른쪽 자식으로 2가 삽입 되었다.

다음은 새로운 노드와, 부모 노드의 값을 비교한다.

• 첫 번째 비교 시, 부모 노드는 6, 자식 노드는 2 이므로 두 노드의 위치가 교환 된다.
• 두 번째 비교에서도 부모 노드는 3, 자식 노드는 2 이므로, 두 노드의 위치가 교환 된다.
• 세 번째 비교 시 부모 노드의 값이 1로 더 작으므로, 자리 변경을 마치게 된다.

이번엔 두 가지 함수, compare_with_parent와 insert 함수를 구현해보자.

MAX_HEAP_SIZE = 101

class Heap:
    def __init__(self):
        self.arr = [None] * MAX_HEAP_SIZE
        self.heap_count = 0

    def compare_with_parent(self, index):
        if index <= 1:
            return False
        parent_index = index // 2
        if self.arr[index] < self.arr[parent_index]:
            return True
        else:
            return False

    def insert(self, data):
        self.heap_count += 1
        if self.heap_count == 1:
            self.arr[self.heap_count] = data
            return

        self.arr[self.heap_count] = data
        insert_index = self.heap_count

        while self.compare_with_parent(insert_index):
            parent = insert_index // 2
            self.arr[insert_index], self.arr[parent] = (
                self.arr[parent],
                self.arr[insert_index],
            )
            
            insert_index = parent
        # print(self.arr[1 : self.heap_count + 1])
        return True

heap = Heap()
heap.insert(1)
heap.insert(3)
heap.insert(4)
heap.insert(5)
heap.insert(6)
heap.insert(7)
heap.insert(8)
heap.insert(9)
heap.insert(10)
heap.insert(11)
heap.insert(2)

📌 힙에서 데이터 추출

힙에서는 항상 루트 노드의 데이터를 추출해 낸다.
즉, 최소 힙이면 힙의 최소 값이 추출되고, 최대 힙이면 힙의 최대 값이 추출된다.

첫 번째로, 루트 노드를 추출한다.
루트 노드를 추출하게 되면 3과 4로 이어지던 갈 곳 잃은 간선 두 개가 남는다. 다음 단계로 이동하자.

비어있는 루트 노드의 자리를 빨리 채워줘야 한다. 가장 마지막 노드를 루트 노드 위치로 옮긴다. 11번 노드가 루트 노드로 옮겨간다.

2번 과정에서 마지막 노드를 이동 시켰기 때문에, 부모 노드가 자식 노드보다 값이 작아야 한다는 힙의 규칙이 깨져 있는 상태이다. 이 규칙이 다시 성립되도록 루트 노드의 위치를 변경해줘야 한다.

데이터 삽입에선 아래에서 위로 올라오면서 비교했다면, 이번엔 위에서 아래로 내려가면서 값을 비교하고, 위치를 변경하는 것이이다.

위치가 변경되지 않을 때까지 위치를 이동 시키게 되면, 이 트리는 다시 최소 힙의 규칙을 지키게 된다.

📌 데이터 삭제 구현

MAX_HEAP_SIZE = 101

class Heap:
		# ... 이전 코드 ...

    def compare_with_child(self, index):
        left = 2 * index
        right = 2 * index + 1

        if self.arr[left] == None and self.arr[right] == None:
            return False

        if self.arr[right] == None:
            if self.arr[left] < self.arr[index]:
                return left
            else:
                return False

        if self.arr[left] < self.arr[right]:
            return left
        else:
            return right

    def pop(self):
        index = 1
        root = self.arr[1]

        terminal_data = self.arr[self.heap_count]
        self.arr[self.heap_count] = None
        self.arr[index] = terminal_data
        self.heap_count -= 1

        while True:
            child_index = self.compare_with_child(index)
            if not child_index:
                break

            self.arr[child_index], self.arr[index] = (
                self.arr[index],
                self.arr[child_index],
            )
            index = child_index

        return root

heap = Heap()
heap.insert(1)
heap.insert(3)
heap.insert(4)
heap.insert(5)
heap.insert(6)
heap.insert(7)
heap.insert(8)
heap.insert(9)
heap.insert(10)
heap.insert(11)

print(heap.arr[1 : heap.heap_count + 1])
print(heap.pop())
print(heap.arr[1 : heap.heap_count + 1])
print(heap.pop())
print(heap.arr[1 : heap.heap_count + 1])

📌 우선순위 큐

힙은 어디에 주로 사용될까 ❓

실행해야 할 작업이나 프로세스에 우선순위가 매겨져 있을 때, 힙을 사용하면 데이터를 저장하기 위한 우선순위 큐를 구현할 수 있다.

MAX_HEAP_SIZE = 101

class Heap:
    def __init__(self):
        self.arr = [None] * MAX_HEAP_SIZE
        self.heap_count = 0

    def compare_with_parent(self, index):
        if index <= 1:
            return False
        parent_index = index // 2
        if self.arr[index] < self.arr[parent_index]:
            return True
        else:
            return False

    def insert(self, data):
        self.heap_count += 1
        if self.heap_count == 1:
            self.arr[self.heap_count] = data
            return

        self.arr[self.heap_count] = data
        insert_index = self.heap_count

        while self.compare_with_parent(insert_index):
            parent = insert_index // 2
            self.arr[insert_index], self.arr[parent] = (
                self.arr[parent],
                self.arr[insert_index],
            )

            insert_index = parent
        # print(self.arr[1 : self.heap_count + 1])
        return True

    def compare_with_child(self, index):
        left = 2 * index
        right = 2 * index + 1

        if self.arr[left] == None and self.arr[right] == None:
            return False

        if self.arr[right] == None:
            if self.arr[left] < self.arr[index]:
                return left
            else:
                return False

        if self.arr[left] < self.arr[right]:
            return left
        else:
            return right

    def pop(self):
        index = 1
        root = self.arr[1]

        terminal_data = self.arr[self.heap_count]
        self.arr[self.heap_count] = None
        self.arr[index] = terminal_data
        self.heap_count -= 1

        while True:
            child_index = self.compare_with_child(index)
            if not child_index:
                break

            self.arr[child_index], self.arr[index] = (
                self.arr[index],
                self.arr[child_index],
            )
            index = child_index

        return root

heap = Heap()
heap.insert(1)
heap.insert(3)
heap.insert(4)
heap.insert(5)
heap.insert(6)
heap.insert(7)
heap.insert(8)
heap.insert(9)
heap.insert(10)
heap.insert(11)

print(heap.arr[1 : heap.heap_count + 1])

print(heap.pop())

print(heap.arr[1 : heap.heap_count + 1])

print(heap.pop())

print(heap.arr[1 : heap.heap_count + 1])