Heap tree 만들기 ( make heap )

힙트리에 대해 알고 싶다면 여기 👇🏻

https://p-james-y.tistory.com/9

이진트리 [ 힙 ]

힙트리 만들기 

힙트리로 만들기 위해서는 즉 힙 성질을 만족하는 트리를 만들기 위해서는 "heapify down" 연산을 수행해야 한다.

heapify down 연산이란??
1. 부모노드 key 가 두 자식노드이 key 보다 작은 경우 두 자식 노드 key 중 큰값과 바꿔준다.
2. 1번을 통해 부모노드와 자식노드가 혹시 바뀌었다면 리프노드의 부모노드까지 1번을 반복해준다.
3. 순서는 리프노드를 제외한 가장 밑에 있는 노드부터 루트노드까지 실행시킨다.

그림 예시를 통해 좀 더 알아보자 👏🏻

실제 데이터 리스트 구조

실제 리스트를 가상의 힙트리로 그리면 다음과 같다.

이진트리

위의 트리는 힙성질을 만족하지 않는다.

heapify down 연산을 통해 힙성질을 만족하게 만들어보자!

리프노드(13, 14, 11, 12, 10) 를 제외하고 가장 밑에 있는 노드부터 확인한다. 즉 노드 6을 먼저 확인한다. 노드 6과 노드 6의 두개의 자식노드 13, 14 를 비교해보니 노드 6이 13, 14 보다 값이 작습니다. 따라서 노드 6과 노드 14 ( 노드 13과 노드 14중 높은 값 ) 를 바꿔준다.

부분 힙트리 완성

위의 그림 보라색 부분을 보면 부분 힙트리가 완성된걸 확인할수 있다. 이런식으로 루트노드까지 올라가는 heapify down 연산을 진행해준다. 다음은 노드 4를 확인해보자. 노드4는 노드4의 자식노드 12, 11 보다 키값이 작으므로 노드 4와 노드 12를 바꿔준다.

부분 힙트리

다음으로 노드 9를 확인한다. 노드9의 자식노드는 14, 10이다. 9보다 14, 10이 더 크므로 9와 14를 스와핑 해준다. 단 여기서 작업이 끝나는게 아닌 다시한번 자식 노드로 내려간 노드9와 노드9의 자식노드 13, 6을 확인해준다. 노드 9보다 노드 13이 더 크므로 다시한번 노드 9와 노드 13을 스와핑 해준다. 이번에는 스와핑이 두번 일어났다는 것을 명심하고 그림을 통해 확인해보자.

부분 힙트리

마지막으로 루트노드를 확인해보자. 루트 노드 8는 자식노드 14, 12 보다 작다. 따라서 노드8과 노드14를 바꿔준다. 다시 노드 8의 자식노드 13, 10이 있다. 노드 8보다 키값이 크므로 노드8과 노드13을 바꿔준다. 다시 노드8의 자식노드 9, 6을 비교해서 노드8과 노드9를 바꿔준다. 총 3번의 스와핑이 일어났다.

힙트리 완성

위의 그림을 보면 루트노드까지 모두 힙성질을 만족하는 힙트리가 완성되었다.

 

이제 힙트리 만드는 로직을 코드로 한번 알아보자.

def make_heap(H):
    n = len(H)
    # 리프노드부터 루트노드까지 k = n-1, n-2, ..., 0
    for k in range(n-1, -1, -1):
        heapify_down(k) # H[k] (k 번재 노드) 를 힙성질을 만족하도록 이동

def heapify_down(k):
    while H[k] !== leaf_node:
        left_node, right_node = 2*k + 1, 2*k + 2
        m = index_max(H[k], H[left_node], H[right_node]) # 노드 키값중 가장 큰값을 가지는 인덱스
        if k != m: # 만약 부모노드가 자식노드보다 값이 작다면
            swap(H[k], H[m]) # 노드 스와핑
            k = m # 부모 노드 바꿔준다
        else:
            break

Make heap 시간복잡도

heapify 는 최대 힙의 높이(h) 만큼 시간복잡도가 된다.

높이가 아무리 커봤자 logN 보다는 작다.

리프노드하고 가까운 노드를 heapify down 하는 것이 루트노드에 있는 거를 heapify down 하는 것보다 시간복잡도가 더 작다.

따라서 make heap 의 시간복잡도는 n 이라고 봐도 무방하다.

 

Reference

https://www.youtube.com/watch?v=6VMSTOdHRfI&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=22