11월 자료구조 - 힙(Heap)

 

 

이번에는 힙(Heap) 자료구조를 다뤄보겠습니다. 힙은 주로 우선순위 큐(Priority Queue)를 구현할 때 사용됩니다.

 

 

1. 자료구조 주제

힙 (Heap)

 

2. 고른 자료구조의 정의

힙(Heap)은 완전 이진 트리(Complete Binary Tree)로, 부모 노드가 자식 노드보다 우선순위가 높거나 낮은 특성을 갖는 자료구조입니다. 힙은 크게 두 가지 종류로 나뉩니다:

• 최소 힙(Min Heap): 부모 노드가 자식 노드보다 작거나 같은 값을 가집니다. 따라서 루트 노드는 트리에서 가장 작은 값을 가집니다.
• 최대 힙(Max Heap): 부모 노드가 자식 노드보다 크거나 같은 값을 가집니다. 루트 노드는 트리에서 가장 큰 값을 가집니다.

힙은 주로 우선순위 큐에서 사용되며, 힙을 이용하면 데이터의 삽입과 삭제를 O(log n) 시간 복잡도로 처리할 수 있습니다. 힙을 이용한 알고리즘으로는 다익스트라 알고리즘, 힙 정렬(Heap Sort) 등이 있습니다.

 

3. 고른 자료구조를 구현한 파이썬 코드 전문

파이썬에서는 heapq 모듈을 사용하면 최소 힙을 쉽게 구현할 수 있습니다. 아래는 직접 최소 힙을 구현한 예시입니다.

class MinHeap:
    def __init__(self):
        self.heap = []

    def parent(self, i):
        return (i - 1) // 2

    def left_child(self, i):
        return 2 * i + 1

    def right_child(self, i):
        return 2 * i + 2

    def insert(self, key):
        # 힙에 값을 삽입
        self.heap.append(key)
        self._heapify_up(len(self.heap) - 1)

    def _heapify_up(self, i):
        # 삽입 후 힙 속성 유지 (상향식)
        while i > 0 and self.heap[self.parent(i)] > self.heap[i]:
            self.heap[self.parent(i)], self.heap[i] = self.heap[i], self.heap[self.parent(i)]
            i = self.parent(i)

    def extract_min(self):
        if len(self.heap) == 0:
            return "Heap is empty"
        if len(self.heap) == 1:
            return self.heap.pop()
        
        root = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._heapify_down(0)
        return root

    def _heapify_down(self, i):
        # 삭제 후 힙 속성 유지 (하향식)
        smallest = i
        left = self.left_child(i)
        right = self.right_child(i)

        if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
            smallest = left
        if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
            smallest = right
        if smallest != i:
            self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
            self._heapify_down(smallest)

    def peek(self):
        # 최소값 반환 (삭제하지 않음)
        if len(self.heap) > 0:
            return self.heap[0]
        return "Heap is empty"

# 예시 사용
min_heap = MinHeap()
min_heap.insert(3)
min_heap.insert(1)
min_heap.insert(6)
min_heap.insert(5)
min_heap.insert(9)
min_heap.insert(8)

print("Min value:", min_heap.peek())  # 최소값 출력
print("Extracted min:", min_heap.extract_min())  # 최소값 추출
print("New min value:", min_heap.peek())  # 새로운 최소값 출력

 

4. 고른 자료구조의 원리를 어떻게 파이썬으로 구현했는지

위 코드는 최소 힙(Min Heap)을 파이썬으로 구현한 예시입니다. 코드 해설을 해보겠습니다.

• MinHeap 클래스: MinHeap 클래스는 힙을 나타내며, 힙에서 자주 사용되는 연산들을 메서드로 구현합니다. self.heap 리스트는 힙을 저장하는 자료구조입니다.
• parent, left_child, right_child 메서드: 힙에서 부모와 자식 노드를 찾는 메서드입니다. 각각의 인덱스를 기준으로 부모, 왼쪽 자식, 오른쪽 자식의 인덱스를 계산합니다. 부모 인덱스는 (i - 1) // 2, 왼쪽 자식은 2 * i + 1, 오른쪽 자식은 2 * i + 2입니다.
• insert 메서드: 이 메서드는 새로운 값을 힙에 삽입합니다. self.heap.append(key)를 사용하여 값을 힙의 마지막에 추가한 후, _heapify_up 메서드를 호출하여 힙 속성을 상향식으로 복구합니다.
• _heapify_up 메서드: 삽입된 값을 올바른 위치로 올려주는 메서드입니다. 자식 노드가 부모 노드보다 작으면 두 값을 교환하며, 부모 노드가 더 이상 자식 노드보다 크지 않으면 반복을 종료합니다.
• extract_min 메서드: 이 메서드는 힙의 루트 노드(최소값)를 삭제하고 반환합니다. 루트 노드를 마지막 노드와 교환한 후, _heapify_down 메서드를 호출하여 힙 속성을 하향식으로 복구합니다.
• _heapify_down 메서드: 루트 노드의 자식들 중 가장 작은 값을 부모 노드와 교환하며, 힙 속성을 유지합니다. 자식 노드가 부모 노드보다 작으면 계속해서 교환을 반복합니다.
• peek 메서드: 힙에서 가장 작은 값을 반환합니다. 루트 노드는 항상 최소값을 가지므로 이를 반환합니다.

 

5. 느낀점

힙은 우선순위 큐를 구현하는 데 매우 유용한 자료구조입니다. 특히 삽입과 삭제 연산을 O(log n) 시간 복잡도로 처리할 수 있기 때문에 효율적인 데이터 처리에 적합합니다. 파이썬에서 리스트를 사용하여 힙을 구현하는 과정에서 힙의 상향식과 하향식 속성에 대해 잘 이해할 수 있었습니다. 힙은 다익스트라 알고리즘과 같은 많은 알고리즘에서 중요한 역할을 하므로, 이를 잘 이해하고 활용하는 것이 매우 중요합니다. 직접 구현해보면서 힙의 원리와 효율성에 대해 실감할 수 있었고, 이 자료구조가 실제 문제 해결에 어떻게 쓰일 수 있는지에 대해 더 깊은 이해를 얻을 수 있었습니다.