트리 - 힙 make_heap 연산

1.make_heap이 무엇인가?

make_heap은 힙이 아닌 배열(또는 완전이진트리 형태의 데이터)을 힙 성질을 만족하도록 바꾸는 연산이다.
이 과정을 부모-자식 비교를 통해 재배치하는것. 보통 heapify_down을 반복해서 수행한다

A = [3, 8, 2, 5, 1, 7, 6] 이런 형태의 배열이 있다고 해보자.
이건 그냥 배열이지, 아직 힙이라는 보장은 없다. 이걸 최대 힙 또는 최소 힙 조건에 맞게 다시 정리하는게 make_heap이다.

 

2. 왜 make_heap이 필요할까?

힙은 보통 우선순위 큐에 쓰이는데, 처음부터 데이터가 힙 상태로 들어오는게 아니라 그냥 막 들어온 배열인 경우가 많다.
그럴 때 이 전체 데이터를 한 번에 힙 구조로 바꿔야 이후 find_max, delete_max, insert 같은 연산을 효율적으로 할 수 있다.

 

3. make_heap은 위에서부터가 아니라 아래서부터 고친다.

이게 제일 핵심이다. make_heap은 보통 아래쪽 내부 노드부터 시작해서 위로 올라오면서 고친다.
heapify_down을 이용해 배열을 힙으로 만들고, 각 부모 노드에 대해 아래로 내려가며 재배치하는 방식이다.
왜 아래에서부터 해야하는가?
부모를 고치려면 자식 쪽이 어느 정도 정리돼 있어야 하기 때문이다.
그래야 부모가 내려갈 위치를 올바르게 결정할 수 있다.

 

이걸 다른식으로 말하면 리프(leaf)는 이미 힙이다.
예를 들어 값이 8 하나만 있는 노드가 있다면, 그 노드는 최소 힙이냐 최대 힙이냐를 따질 필요도 없이 이미 조건을 어기지 않는다.
그래서 make_heap은 이렇게 생각하면 된다.

• 맨아래 노드들은 이미 괜찮다.
• 그 부모를 본다.
• 부모가 자식들과의 관계를 어기면 자리를 바꾼다.
• 그걸 한 층씩 위로 올라가며 반복한다.
• 마지막에 루트까지 정리되면 전체가 힙이 된다.

즉 "작은 부분부터 힙으로 만들고, 그걸 합쳐서 전체 힙을 만든다."

 

4. heapify_down이 뭔가?

heapify_down은 어떤 노드 하나가 힙 성질을 어겼을 때, 그 노드를 아래로 내려 보내면서 제자리 찾게하는 연산이다.

최대 힙 기준으로 설명해보자면
어떤 부모 노드가 있는데, 그 자식들보다 값이 작다? 그럼 최대 힙 조건을 어긴 것이다.
이때는 그 부모를 아래로 내려보내야 한다.
방법은 아래와 같다.

1. 왼쪽 자식, 오른쪽 자식 중 더 큰 자식을 찾는다.
2. 부모와 비교한다.
3. 부모가 더 작으면 더 큰 자식과 자리를 바꾼다.
4. 바꾼 뒤, 부모가 내려간 그 자리에서 다시 같은 작업을 반복한다.

즉, 부모가 자기보다 더 강한 자식을 만나면 계속 아래로 밀려나는 거다.

 

5. 예제 (miro를 통해 작성해보자)

배열 A = [4, 1, 7, 3, 8, 5]
완전이진트리로 보면 아래의 형태와 같다.

 

           4
         /   \
        1     7
       / \   /
      3   8 5

이 상태에서 최대 힙으로 만들고 싶다. 최대 힙이면 부모가 자식보다 커야 한다.
그런데 지금 보면

• 1의 자식이 3,8이다.
• 1은 8보다 작다

즉, 여기서 이미 힙 조건이 깨져 있다. 

아래 그림으로 heapify_down 연산 이해해 보자

[그림1] heapify_down 연산

6.make_heap의 본질

make_heap은 단순히 "바꾸는 기술"이 아니다.

사고 방식이 있는데 그것은
"큰 문제를 한 번에 해결하지 말고, 아래쪽은 작은 부분부터 힙으로 만든 다음, 그것을 위로 합쳐라."

즉,

• 리프는 이미 힙
• 리프의 부모를 힙으로 만듦
• 그 위 부모를 힙으로 만듦
• 결국 루트까지 올라가면서 전체가 힙

이런 구조이다.
그래서 make_heap은 bottom-up 방식 이라고 부른다.

아래에서, 최대 힙을 어떻게 구현했는가 확인할 수 있다.

class Maxheap:
    def __init__(self):
        self.array = [] 

    def heapify_down(self, k, n): 
        while 2 * k + 1 < n: 
            left = 2 * k + 1 
            right = 2 * k + 2 
            larger = left 

            if right < n and self.array[right] > self.array[left]:
                larger = right 

            if self.array[k] >= self.array[larger]: 
                break 

            self.array[k], self.array[larger] = self.array[larger], self.array[k] 
            k = larger 
    
    def make_heap(self):
        n = len(self.array)
        for k in range((n - 2) // 2, -1, -1): 
            self.heapify_down(k, n)

#최대 힙 예시
H = Maxheap()
H.array = [7, 4, 5, 3, 8, 9]
H.make_heap()
print(H.array) # [9, 8, 7, 3, 4, 5] 최대 힙 형태로 바뀌었음