힙 - Heaps

정의

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

1. 루트 노드가 언제나 최댓값 또는 최솟값을 가짐
   1. 최대 힙(max heap), 최소 힙(min heap)
2. 완전 이진 트리여야 함

📌 재귀적으로도 정의가 가능하다. max heap의 경우 어느 노드를 루트로 하는 서브트리인 경우에도 모두 최대 힙의 조건을 만족한다.

 

이진 탐색 트리와의 비교

1. 원소들은 완전히 크기 순으로 정렬되어 있는가? 이진 탐색 트리 O, 힙 X
2. 특정 키 값을 가지는 원소를 빠르게 검색할 수 있는가? 이진 탐색 트리 O, 힙 X
3. 부가 제약 조건은 어떤것인가? 힙은 이진 탐색 트리에 비해 완전 이진 트리여야 한다는 부가 제약 조건을 갖고 있다.

 

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

• 연산의 정의
  • __init__() : 빈 최대 힙을 생성
  • insert(item) : 새로운 원소를 삽입
  • remove() : 최대 원소(root node)를 반환, 그리고 동시에 이 노드를 삭제

데이터 표현의 설계

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

트리에선 다음 특질을 이용할 수 있다. 루트 노드를 1번, 왼쪽 자식부터 2, 오른쪽 자식 3번이라 하고 계속 이런식으로 다음 레벨에서도 관계가 이어진다면

 

노드 번호 m을 기준으로

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

📌 완전 이진 트리이므로 노드의 추가/삭제는 마지막 노드에서만 이뤄진다.

 

코드 구현 - 빈 힙 생성

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

 

최대 힙에 원소 삽입

• 트리의 마지막 자리에 새로운 원소를 임시로 저장
• 부모 노드와 대소 비교를 통해 크다면 계속 위로 이동시킨다.
• 복잡도 : 원소의 개수가 n인 최대 힙에 새로운 원소를 삽입한다면?
  • 루트 노드까지 갈수도 있으니까 $\log_2 n$ 이다.

삽입 연산의 구현 - insert(item) 메서드

class MaxHeap():
    def __init__(self):
        self.data = [None]
        
    def insert(self, item):
        pass

class MaxHeap:

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


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

def solution(x):
    return 0

최대 힙에서 원소 삭제

1. 루트 노드의 제거 - 이것이 원소들 중 최댓값
2. 트리 마지막 자리 노드를 임시로 루트 노드의 자리에 배치
3. 자식 노드들과의 값 비교와 아래로, 아래로 이동
   1. 자식 둘중 어디로 이동할 것인지 결정하면서
4. 시간 복잡도: 원소의 개수가 n인 최대 힙에서 최대 원소 삭제 -> 자식 노드들과의 대소 비교 최대 회수 = 2 * $\log_2 n$ = $\log_2 n$

삭제 연산의 구현 - remove() 메서드

class MaxHeap():
    def __init__(self):
        self.data = [None]
        
    def insert(self, item):
        pass
    
    def maxHeapify(self, i):
        pass
    
    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

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 child) 의 인덱스를 계산합니다.
        left = 2*i

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

        smallest = i
        # 왼쪽 자식이 존재하는지, 그리고 왼쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
        if left < len(self.data) and self.data[left] > self.data[smallest]:
            # 조건이 만족하는 경우, smallest 는 왼쪽 자식의 인덱스를 가집니다.
            smallest = left

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

최대 최소 힙의 응용

1. 우선 순위 큐(priority queue)
   1. Enqueue 할 때 '느슨한 정렬'을 이루고 있도록 함 $O(\log_2 n)$
   2. Dequeue 할 때 최댓값을 순서대로 추출 $O(\log_2 n)$
2. 힙 정렬(heap sort)
   1. 정렬되지 않은 원소들을 아무 순서로나 최대 힙에 삽입: $O(\log_2 n)$
   2. 삽입이 끝나면, 힙이 비게 될때까지 하나씩 삭제: $O(\log_2 n)$
   3. 원소들이 삭제된 순서가 원소들의 정렬 순서
   4. 정렬 알고리즘의 복잡도 : $O(n\log_2 n)$