[Tech, etc.] Heapify(힙 생성)

Heapify

:Heapify is the process of creating a heap data structure from a binary tree represented using an array.

: Heapify란 배열(Array)로 표현된 이진 트리(Binary tree)의 자료구조를 갖는 힙(Heap)을 생성하는 과정이다.

 

 알고리즘 과제로 Heap을 Build하는 문제에 대해 알고리즘을 제시해야했고, 목표 시간복잡도(Time-Complexity)는 Linear time(O(n))이었다. Heap을 접할 때 기본적으로 함께 알게 되는 함수 중 하나가 Insert() 함수다. Insert() 함수의 시간복잡도는 Tree의 Height(높이)만큼 비교가 필요해 O(log n)이다. 이를 n개의 노드(node)를 Insert()하는 방식으로 Heap을 생성한다면 O(n * log n)의 시간복잡도를 구할 수 있지만, Tree의 특성을 이용한다면 O(n)으로 줄일 수 있다.

 기본적인 아이디어는 각 level에서 Tree의 node 개수와 해당 level로부터 최하단 노드(leaf nodes)까지의 거리(degree)를 이용하는 것이고, 분할 정복(Divide and Conquer)도 적용된다. Max-Heap을 Heapify로 구성해보자. Tree의 최하단 부인 leaf nodes부터 시작하면 leaf nodes의 개수는 전체 node 개수인 n의 반인 n/2이고, leaf nodes의 height는 0이다. node의 개수는 n/2로 많지만 height가 0으로 자식 노드(child node)가 없기에 비교 대상이 없다. leaf nodes의 parent nodes를 보면, leaf nodes 개수의 절반인 n/(2^2)이며 height는 1인 것을 알 수 있다. child nodes를 갖기에 parent node와 child node(1개던 2개던)의 크기 비교를 통해 2개 혹은 3개로 구성된 작은 Max-Heap을 구성할 수 있다. 여기서 필요한 연산의 개수는 현재 level의 node 개수(n/2)를 height(1)번 계산한 1 * n/(2^2)임을 알 수 있다. 현재 level의 바로 상위 level은 n/(2^3)개의 node를 갖고 height는 2를 갖는다. 따라서 해당 level에선 2 * n/(2^3)번의 계산이 필요하다. 이를 일반식으로 나타내면 아래와 같고 계산해보면 Linear time인 O(n)을 갖는다는 걸 알 수 있다. (열거된 수식에서 n/4 * c로 넘어가는 부분은 마스터 정리(Master Theorem)을 적용할 수 있다.)

Pseudo Code(수도 코드)는 다음과 같다.

def Heapify(Arr, idx, heapSize):
    mid = idx/2
    left = 2 ∗ mid + 1
    right = 2 ∗ mid + 2
    if left < heapSize and Arr[left] > Arr[mid] then
        mid = left
    end if
    if right < heapSize and Arr[right] > Arr[mid] then
        mid = right
    end if
    if mid != idx then
        Swap(Arr[mid], Arr[idx/2])
        Heapify(Arr, mid)
    end if

 

 

참고

- https://www.geeksforgeeks.org/heap-sort/

Heap Sort - GeeksforGeeks

- https://www.growingwiththeweb.com/data-structures/binary-heap/build-heap-proof/

Binary heap: Build heap proof

- https://ratsgo.github.io/data%20structure&algorithm/2017/09/27/heapsort/

힙 정렬(Heap Sort) · ratsgo's blog

- https://ordo.tistory.com/88