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

illstandtall·2021년 4월 29일
0

Programmers dev course

목록 보기
16/34
post-thumbnail

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


이진 트리의 응용 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)$

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

profile
주니어

관심 있을 만한 포스트

0개의 댓글