힙 자료구조 - make heap 연산

https://hkim-data.tistory.com/187

힙 자료구조

이전 포스팅에 이어서 make heap 연산에 대해 알아보자

 

입력값은 힙성질을 만족하고 있지 않다.

힙 성질을 만족하기 위해, heapify - down을 계속해서 진행하면 된다.

리스트의 맨 오른쪽 인덱스부터 A[0]까지 계속해서 반복

1. 리프노드면 내버려둠

2. 자식 노드가 있을 때 나보다 클 때 A [2*k+1]과 A [2*k+2] 값 중 큰 것이랑 변경

3. 변경 후 리프 노드가 아니면 또 아래랑 비교해줘야 함

 

def make_heap(A):
    # O(n * t) -> 리스트 길이 n 만큼 heapify_down의 수행시간 t 반복
    n = len(A)
    for k in range(n-1, -1, -1):
        # A[k] -> heap 성질 만족하는 곳으로
        heapify_down(k,n)

def heapify_down(k,n):
    # 최악의 경우 가장 작은 값이 루트에 있을 경우임 이는 높이만큼 반복하게 됨
    # while 내부의 코드는 모두 상수시간임
    # 즉 O(nh) -> h는 2^h-1 < h <= logn 즉 O(nlogn)이지만 리프노드는 연산을 하지 않아도 되기 때문에 실제로는 O(n)임
    # A[k], n 값
    while A[k] != leafnode:
        L, R = 2*k+1, 2*k+2
        m = max(A[k], A[L], A[R])
        if k != m : # 변경 될 때
            # 변경 코드 A[k] <-> A[m]
            A[k], A[m] = A[m], A[k]
            k = m
        else:
            break

h 개념