힙(Heap) 이란?

데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리

🔍 최댓값이 맨 위인 힙을 Max heap, 최솟값이 맨 위인 힙을 Min heap 이라고 한다

Max Heap

항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있어야 한다

1. 원소 추가

• 시간 복잡도 : $O(logN)$

class MaxHeap:
    def __init__(self):
        # 완전 이진 트리를 배열로
        self.items = [None]

    def insert(self, value):
        
        # 1. 새 값을 맨 끝에 넣는다
        self.items.append(value)

        cur_index = len(self.items) - 1

		# 2. 최 상위 까지 반복
        while cur_index > 1:

            parent_index = cur_index // 2

			# 부모랑 비교
            if self.items[cur_index] > self.items[parent_index]:
                self.items[cur_index], self.items[parent_index] = self.items[parent_index], self.items[cur_index]
                cur_index = parent_index
            else:
                break;
                
        return

2. 원소 제거

• 루트 노드를 삭제하는 것
• 원소를 삭제할 때도 힙의 규칙이 지켜져야 한다

def delete(self):
        
        # index 1 과 맨끝을 교환
        self.items[1], self.items[-1] = self.items[-1], self.items[1]

        # 맨끝으로 이동한 최댓값을 뽑아냄
        max_data = self.items.pop()

        # 맨위로 올라간 맨끝 요소의 인덱스
        cur_index = 1

        # 끝까지 비교
        while cur_index <= len(self.items) - 1 :
            left_child_index = cur_index * 2
            right_child_index = cur_index * 2 + 1
            max_index = cur_index

            # 왼쪽 자식이 있다 
            if left_child_index <= len(self.items) -1 and self.items[left_child_index] > self.items[max_index] :
                max_index = left_child_index

            # 오른쪽 자식이 있다.
            if right_child_index <= len(self.items) -1 and self.items[right_child_index] > self.items[max_index] :
                max_index = right_child_index

            # 현재 인덱스가 제일 크다. 교체 x
            if max_index == cur_index:
                break    

            self.items[cur_index], self.items[max_index] = self.items[max_index], self.items[cur_index]
            cur_index = max_index

        return max_data