트리 - 힙 insert 연산

1. 힙 이란?(다시 한 번 짚고 넘어가자)

힙은 완전이진트리 형태를 가지면서, 동시에 부모와 자식 사이의 대소관계를 만족하는 자료구조 이다.

따라서,  부모가 자식보다 크기만 하다고 해서 다 힙은 아니다.

예를 들어보자. 

      10
     /  \
    8    9
   /
  7

이건 완전이진트리라서 힙이 될 수 있다.

      10
     /  \
    8    9
     \
      7

이건 부모-자식 크기 관계는 맞아도, 완전이진트리 모양이 아니므로 힙이 아니다.

왜냐하면, 왼쪽 자식의 왼쪽이 비었는데 오른쪽이 차 있으므로, 힙이 아니다.

 

2. insert 연산 과정

step1. 초기 상태 array = [ 5, 7, 9, 10, 8, 6 ]에서 make_heap()으로 정렬한다. 

[그림1]최대 힙 상태의 트리

step2. 마지막 위치에 insert 배열은 array = [10, 8, 9, 7, 5, 6, 14] 상태가 된다.

[그림2] 맨 뒤에 append

step3. heapify_up 시작(핵심), 기준은 부모보다 크면 위로 올라간다

[그림3] 아래서 부터 위로 heapify_up

최종. 결과

[그림4] 최종 결과이다.

 

3. insert 연산 핵심

1. insert는 항상 마지막 위치에 삽입한다.
2. 부모와 비교하면서 위로 올라간다(heapify_up)
3. 부모보다 작아지는 순간 멈춘다.

4. heapify_up 핵심

1. 자식끼리 비교하지 않는다.
2. 형제랑 비교하지 않는다.
3. 전체 탐색 하지 않는다.
4. 오직, 현재 노드와 부모 노드만 비교한다.

5. Python으로 구현

class MaxHeap:
    def __init__(self):
        self.array = [] #빈 배열 생성
        
    def heapify_up(self, k):
        while (k > 0) and (self.array[(k - 1 ) // 2] < self.array[k]):
            self.array[k], self.array[(k - 1) // 2] = self.array[(k - 1) // 2], self.array[k]
            k = (k - 1) // 2
            
    def insert(self, k):
        self.array.append(k) 
        self.heapify_up(len(self.array) - 1)