힙(Heap)

1 힙(Heap) 이란?

• 조건이 추가된 이진 트리의 한 종류 → 이진 힙 (Binary Heap)
  • (재귀적 정의) 어느 노드를 루트로 하는 서브트리도 모두 최대 힙
• 힙의 조건

  1. 루트 노드가 언제나 최댓값 또는 최솟값을 갖는다

     • 최대 힙(max heap), 최소 힙(min heap)

  2. 완전 이진 트리여야 한다

     완전 이진 트리

     • 높이 k인 완전 이진 트리
     • 레벨 k-2 까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리
     • 레벨 k-1에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진 트리

2 이진 탐색 트리와의 비교

	이진 탐색 트리	힙
원소들은 완전히 크기 순으로 정렬되어 있는가?	O	X (느슨한 정렬)
특정 키 값을 갖는 원소를 빠르게 검색할 수 있는가?	O	X
부가의 제약 조건은 어던 것인가?	-	완전 이진 트리여야 한다

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

16.3.1 데이터 표현의 설계

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

• 배열을 이용한 이진 트리의 표현
• 노드 번호 m을 기준으로
  • 왼쪽 자식의 번호: 2 * m
  • 오른쪽 자식의 번호: 2 * m + 1
  • 부모 노드의 번호: m // 2
• 완전 이진 트리이므로 노드의 추가 / 삭제는 마지막 노드에 대해 진행

3.2 연산의 정의

• init(): 빈 최대 힙을 생성한다

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

• insert(item): 새로운 원소를 삽입한다

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

  2. 부모 노드와 키 값을 비교하여 위로, 위로 이동 (자리를 바꾸며)

     → 제약 조건을 만족할 때까지 이동

  • 시간 복잡도
    • 원소의 개수가 n인 최대 힙에 새로운 원소 삽입 → 부모 노드와의 대소 배교 최대 횟수: $log_2n$ → 트리의 높이: $log_2n$ ⇒ 최악의 복잡도 O($logn$)의 삽입 연산
      

class MaxHeap:
		def insert(self, item):
        self.data.append(item)
	    
        new = len(self.data) - 1
        parent = new // 2
        
        while new > 1 and self.data[parent] < self.data[new]:
            self.data[parent], self.data[new] = self.data[new], self.data[parent]
            new, parent = parent, parent//2

• remove(): 최대 원소 (root node)를 삭제하고 동시에 반환한다
  1. 루트의 노드의 제거 - 이것이 원소들 중 최댓값
  2. 트리 마지막 자리 노드를 임시로 루트 노드의 자리에 배치
  3. 자식 노드들과의 값 비교와 아래로, 아래로 이동
     1. 자식이 둘일 경우, 더 큰 값 선택
  • 시간 복잡도

    • 자식 노드들과의 대소 비교 최대 횟수: 2 * $log_2n$

      ⇒ 최악의 복잡도 O($logn$)의 삭제 연산

class MaxHeap:
		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 = i * 2

        # 오른쪽 자식 (right child) 의 인덱스를 계산합니다.
        right = i * 2 + 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 는 오른쪽 자식의 인덱스를 가집니다.
            samllest = right

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

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

4 최대 / 최소 힙의 응용

4.1 우선 순위 큐(priority queue)

• euqueue할 때 느슨한 정렬을 이루고 있도록 함 → $O(logn)$
• dequeue할 때 최댓값을 순서대로 추출 → $O(logn)$

→ 양방향 연결 리스트로 구현했을 때보다 효율적

4.2 힙 정렬 (heap sort)

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

def heapsort(unsorted):
		H = MaxHeap()
		
		for item in unsorted:
				H.insert(item)
		sorted = []
		d = H.remove()
		while d:
				sorted.append(d)
				d = H.remove()
		
		return sorted

5 시간 복잡도

• 힙 구성 (heapify) → $O(NlogN)$
  
• 삽입 (insert) → $O(logN)$
  
• 삭제 (remove) → $O(logN)$

6 파이썬에서의 힙 활용

import heapq

heapq.heapify(L) # 리스트 L로부터 min heap 구성
m = heapq.heappop(L)  # min heap L에서 최솟값 삭제 (반환)
heapq.heappush(L, x) # min heap L에 원소 x 삽입