[프로그래머스 강의] 22강 힙(Heaps)(1)

힙(Heaps)

---

힙(Heap)이란?

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

 

1.  루트(root) 노드가 언제나 최댓값 또는 최솟값을 가진다. 

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

2. 완전 이진 트리  

 

 

• 완전 이진 트리란 각 노드가 최대 2개의 자식 노드를 갖는 트리 형태의 자료구조 로서 마지막 레벨을 제외한 모든 노드는 완전히 채워져 있어야 한다. 
•  최하단 레벨의 노드는 좌측만 노드가 채워져 있거나 좌측과 우측 모두 채워져 있어야 한다. 노드를 삽입할 때는 최하단 좌측 노드부터 차례대로 삽입해야 한다.

---

최대 힙(max heap)의 추상적 자료 구조

 

재귀적으로도 정의된다. 즉, 어느 노드를 루트로 하는 서브 트리도 모두 최대 힙 이다. 

 

연산의 정의

• __init__():  빈 최대 힙 을 생성한다.
• insert(item): 새로운 원소를 삽입한다.
• remove(): 최대 원소 (root node)를 반환하며 동시에 이 노드를 삭제한다. 

---

데이터 표현의 설계

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

 

노드 번호 m을 기준으로,

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

 

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

 

---

최대 힙(max heap)에 원소 삽입

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

2. 부모 노드와 키 값을 비교하여 위로 이동한다. 

 

---

최대 힙(max heap) 원소 삽입의 시간 복잡도

원소의 개수가 n인 최대 힙에 새로운 원소 삽입 시

→ 부모 노드와의 대소 비교 최대 횟수: log n (트리의 높이)

 

최악 복잡도 역시 O(logn) 의 삽입연산이다. 

 

---

문1. 최대 힙에 새로운 원소 삽입

class MaxHeap:

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


    def insert(self, item):
        self.data.append(item)

        idx = len(self.data)-1

        while idx != 1 :
            if self.data[idx//2] < self.data[idx]:
                self.data[idx], self.data[idx//2] = self.data[idx//2], self.data[idx]
                idx = idx//2
            else:
                break


def solution(x):
    return 0