[어서와! 자료구조와 알고리즘은 처음이지?] 08. 힙

본 문서는 어서와! 자료구조와 알고리즘은 처음이지? 강의를 보고 제 주관대로 정리한 글입니다.

---

힙 (Heap)

• 이진 트리의 한 종류
• 루트(Root) 노드가 언제나 최댓값 또는 최솟값을 가짐
  • 최대 힙(Max Heap), 최소 힙(Min Heap)
• 완전 이진 트리여야 함

이진 탐색 트리와의 비교

1. 원소들은 완전히 크기 순으로 정렬되어 있는가?
   • 이진 탐색 트리는 그렇지만 힙은 아님
2. 특정 키 값을 가지는 원소를 빠르게 검색할 수 있는가?
   • 이진 탐색 트리에서는 가능하지만 힙은 아님
3. 부가의 제약 조건은 어떤 것인가?
   • 힙은 완전 이진 트리여야 함

최대 힙(Max Heap)

• 재귀적으로 정의할 수 있음
  • 어느 노드를 루트로 하는 서브트리도 모두 최대 힙

최대 힙 (Max Heap)

연산의 정의

• __init__() - 빈 최대 힙을 생성
• insert(item) - 새로운 원소 삽입
• remove() - 최대 원소(Root Node)를 반환 및 삭제

데이터 표현의 설계

배열을 이용한 이진 트리의 표현

• 노드 번호 m을 기준으로
  • 왼쪽 자식의 번호: 2 * m
  • 오른쪽 자식의 번호: 2 * m + 1
  • 부모 노드의 번호: m // 2
• 완전 이진 트리이므로
  • 노드의 추가/삭제는 마지막 노드에서만

0	1	2	3	4	5	6	7	8	9	10
-	30	24	12	18	21	8	6	4	2	19

최대 힙에 원소 삽입

1. 트리의 마지막 자리에 새로운 원소를 임시로 저장
2. 부모 노드와 키 값을 비교하여 위로, 위로, 이동

• 원소의 개수가 n인 최대 힙에 새로운 원소 삽입
  • 부모 노드와의 대소 비교 최대 회수: log₂n
• 최악 복잡도 O(logn) 삽입 연산

최대 힙에서 원소 삭제

1. 루트 노드의 제거 - 이것이 원소들 중 최댓값
2. 트리 마지막 자리 노드를 임시로 루트 노드의 자리에 배치
3. 자식 노드들과의 값 비교와 아래로, 아래로 이동
   • 자식은 둘 있을 수 있는데, 어느 쪽으로 이동

• 원소의 개수가 n인 최대 힙에서 최대 원소 삭제
  • 자식 노드들과의 대소 비교 최대 회수: 2 x log₂n
• 최악 복잡도 O(logn)의 삭제 연산

class MaxHeap:
    def __init__(self):
        self.data = [None]

    def insert(self, item):
        self.data.append(item)

        cur = len(self.data) - 1
        parent = cur // 2

        while parent and self.data[cur] > self.data[parent]:
            self.data[cur], self.data[parent] = self.data[parent], self.data[cur]
            cur = parent
            parent //= 2

    def remove(self):
        if len(self.data) <= 1:
            return None

        self.data[1], self.data[-1] = self.data[-1], self.data[1]
        data = self.data.pop(-1)
        self.max_heapify(1)

        return data

    def max_heapify(self, i):
        # 왼쪽 자식 (left child) 의 인덱스를 계산합니다.
        left = i * 2

        # 오른쪽 자식 (right child) 의 인덱스를 계산합니다.
        right = i * 2 + 1

        biggest = i

        # 왼쪽 자식이 존재하는지, 그리고 왼쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
        if left < len(self.data) and self.data[left] > self.data[biggest]:
            biggest = left

        # 오른쪽 자식이 존재하는지, 그리고 오른쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
        if right < len(self.data) and self.data[right] > self.data[biggest]:
            biggest = right

        if biggest != i:
            # 현재 노드 (인덱스 i) 와 최댓값 노드 (왼쪽 아니면 오른쪽 자식) 를 교체합니다.
            self.data[biggest], self.data[i] = self.data[i], self.data[biggest]

            # 재귀적 호출을 이용하여 최대 힙의 성질을 만족할 때까지 트리를 정리합니다.
            self.max_heapify(biggest)

최대/최소 힙의 응용

우선순위 큐 (Priority Queue)

• Enqueue 할 때 "느슨한 정렬"을 이루고 있도록 함: O(logn)
• Dequeue 할 때 최댓값을 순서대로 추출: O(logn)
• 연결 리스트로 구현한 우선순위 큐와 비교

	연결 리스트	힙
삽입	O(n)	O(logn)
삭제	O(1)	O(logn)

힙 정렬(Heap Sort)

• 정렬되지 않은 원소들을 아무 순서로나 최대 힙에 삽입: O(logn)
• 삽입이 끝나면, 힙이 비게 될때까지 하나씩 삭제: O(logn)
• 원소들이 삭제된 순서가 원소들의 정렬 순서
• 정렬 알고리즘의 복잡도: O(nlogn)

최대 힙 관련 코드는 max_heap.py 참고

def heap_sort(unsorted):
    H = MaxHeap()
    for item in unsorted:
        H.insert(item)

    sorted = []
    d = H.remove()
    while d:
        sorted.append(d)
        d = H.remove()

    return sorted