힙(Heap)

1) 힙 (Heap)

  - 이진 트리의 한 종류 (이진 힙, binary heap)

  - 루트 (root) 노드가 언제나 최대값/최소값을 가짐 → 최대 힙(max heap), 최소 힙(min heap)

  - 완전 이진 트리여야 함

  - 이진 탐색 트리와 조금 다른 특징을 가짐

    → 서브트리보다 항상 큰 키를 갖고으며 위로 올라갈수록 큰 값을 가지지만, 왼쪽 서브트리와 오른쪽 서브트리 간 관계가 정의 되어있지 않다

 

 

2) 최대 힙(Max Heap)의 추상적 자료구조

①연산의 정의

  - __init__() : 빈 최대 힙 생성

  - insert(item) : 새로운 원소를 삽입

  - remove() :  최대 원소 (root node)를 반환과 동시에 해당 노드 삭제

 

② 데이터 표현의 설계

  - 노드번호 m을 기준으로

• 왼쪽 자식 노드 번호 : 2 * m
• 오른쪽 자식 노드 번호 : 2 * m + 1
• 부모 노드의 번호 : m // 2

  - 완전 이진 트리라는 조건을 충족하기 때문에 마지막 노드에서만 추가/삭제가 이뤄지므로 힙을 배열을 이용해 구현하기 적합함

 

  1. 최대 힙의 원소 삽입

    (1) 트리의 마지막 자리에 새로운 원소를 임시로 저장

    (2) 부모 노드와 키 값을 비교하며 자신 보다 큰 값을 가진 부모 노드를 만나기 전 까지 위로 이동

      ※ 삽입 연산의 최악 복잡도 : O(logn) → 자식 노드들과의 대소 비교 최대 회수 : 2 * log2 n

 

  2. 최대 힙의 원소 삭제

    (1) 루트 노드의 제거 

    (2) 트리 마지막 자리 노드를 임시로 루트 노드의 자리에 배치

    (3) 자식 노드들과의 값 비교로 자신 보다 작은 값을 가진 자식 노드를 만나기 전 까지 아래로 이동

      → 자식 노드가 두 개면 더 큰 키값을 가진 쪽으로 이동

      ※ 삽입 연산의 최악 복잡도 : O(logn) → 자식 노드들과의 대소 비교 최대 회수 : 2 * log2 n

class MaxHeap:

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


    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        								# 왼쪽 자식 (left child) 의 인덱스를 계산합니다.
        right = i * 2 + 1        							# 오른쪽 자식 (right child) 의 인덱스를 계산합니다.
        smallest = i        								# 왼쪽 자식이 존재하는지, 그리고 왼쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
        if left < len(self.data) and self.data[smallest] < self.data[left] :            # 조건이 만족하는 경우, smallest 는 왼쪽 자식의 인덱스를 가집니다.
            smallest = left       							# 오른쪽 자식이 존재하는지, 그리고 오른쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
        if right < len(self.data) and self.data[smallest] < self.data[right]:           # 조건이 만족하는 경우, smallest 는 오른쪽 자식의 인덱스를 가집니다.
            smallest = right
        if smallest != i:            							# 현재 노드 (인덱스 i) 와 최댓값 노드 (왼쪽 아니면 오른쪽 자식) 를 교체합니다.
            self.data[smallest], self.data[i] = self.data[i], self.data[smallest]       # 재귀적 호출을 이용하여 최대 힙의 성질을 만족할 때까지 트리를 정리합니다.
            self.maxHeapify(smallest)


def solution(x):
    return 0

 

 

3) 최대/최소 힙의 응용

① 우선 순위 큐 (priority queue)

  - Enqueue 할 때 '느슨한 정렬'을 이루고 있도록 함 : O(logn)

  - Dequeue 할 때 최댓값을 순서대로 추출 : O(logn)

② 힙 정렬 (heap sort)

  - 정렬되지 않은 원소들을 아무 순서로나 최대 힙에 삽입 : O(logn)

 - 삽입이 끝나면, 힙이 비게 될 때까지 하나씩 삭제 : O(logn)

 - 원소들이 삭제된 순서가 원소들의 정렬 순서

 - 정렬 알고리즘의 복잡도 : O(n * logn)