[Programmers] 15. 기본 자료구조: 트리 (Tree) (4): 이진 트리의 응용 (2): 힙 (heap)

오류에 대한 지적이나 질문, 토의 환영합니다. 자유롭게 댓글 남겨주세요!.!

---

이진 트리의 응용 2

힙 (Heap)

• 이진 트리의 한 종류입니다.
• 루트 노드가 언제나 최대값 또는 최소값을 가집니다.
  • 최대 힙, 최소 힙
• 완전 이진트리여야 합니다.
• 최대/최소 힙 내의 임의의 노드를 루트로 하는 서브 트리 또한 최대/최소 힙입니다.
• 힙 정렬에 사용됩니다.

---

• 최소 힙
  

---

이진 탐색 트리와의 비교

• 힙의 원소들은 크기 순으로 정렬되어 있지 않음
• 특정 키 값을 가지는 빠른 검색이 어렵다

힙의 장점

• 힙은 완전 이진트리여야 하기 때문에 n개의 노드로 이루어진 힙의 높이/깊이는 $log(N) + 1$로 정해집니다.
  그래서 언제나 삽입/삭제 연산의 시간 복잡도는 $log(N)$입니다.
• 노드의 추가와 삭제는 배열의 맨 마지막 원소에서만 일어납니다.

---

힙의 연산

• insert(item): 새로운 원소 item을 힙에 삽입합니다.
• remove(): 최대/최소 원소 (root node)를 삭제하며, 반환합니다.

힙의 구현

• 배열을 이용하는 것이 효율적입니다.
• 노드 번호 $m$을 기준으로 여러 노드의 index를 알 수 있습니다.
  • 왼쪽 자식의 번호: $2*m$
  • 오른쪽 자식의 번호: $2*m + 1$
  • 부모노드의 번호: $m // 2$
• 추가/삭제는 마지막 노드에서만 이루어집니다.

힙의 구현 1. insert()

1. 트리의 마지막 자리(완전 이진트리를 유지하며)에 새로운 원소를 임시 저장합니다.
2. 부모 노드와 키값을 비교하여 부모와 바꾸며 위로 이동합니다.

• 대소비교 횟수: $log(2n)$, 최악 시간 복잡도 O(logn)

def insert(self, item):
    self.data.append(item)
    m = len(self.data) - 1
    while m > 1:
        p = m // 2
        if self.data[p] < self.data[m]:
            self.data[p], self.data[m] = self.data[m], self.data[p]
            m = p
        else:
            break

힙의 구현 2. remove()

1. 루트 노드를 제거합니다.
   • 루트 노드가 원소의 최대/최소 값입니다.
2. 트리의 마지막 자리의 노드를 임시로 루트 노드에 배치합니다.
3. 자식노드와 비교하여 아래로 이동합니다.

• 대소비교 횟수: $2 * log(2n)$, 최악 시간 복잡도 $O(logn)$

def remove(self):
    if len(self.data) > 1:
        self.data[1], self.data[-1] = self.data[-1], self.data[1]
        data = self.data.pop(-1)
        self.maxHeapify(1)
    else:
        data = None
    return data
    
def maxHeapify(self, i):
    left = i*2
    right = i*2 + 1
    smallest = i
    if left < len(self.data) and self.data[left] > self.data[smallest]:
        smallest = left
    if right < len(self.data) and self.data[right] > self.data[smallest]:
        smallest = right
    if smallest != i:        
        self.data[smallest], self.data[i] = self.data[i], self.data[smallest]
        self.maxHeapify(smallest)

---

힙의 응용

우선 순위 큐 (Priority Queue)

• 삽입 할 때 느슨한 정렬을 이루고 있습니다.: $O(logn)$
• 삭제할 때 최대값을 순서대로 추출합니다.: $O(logn)$

힙 정렬 (Heap sort)

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

---

이 글은 프로그래머스 스쿨 인공지능 데브코스 과정에서 공부한 내용을 바탕으로 정리한 글입니다.