Heap tree는 완전이진트리 형태로 모든 부모 노드의 값이 자식 노드 보다 크거나 (max heap) 모든 부모 노드의 값이 자식 노드 보다 작은 (min heap) tree를 말한다. 이 글에서는 max heap tree를 만드는 방법을 알아본다.

Heap tree를 생성하는 buildHeapTree()이 동작하는 절차는 다음과 같다. N은 원소의 갯수.

부모_노드 := 소숫점_버림(N / 2) - 1 부터 0까지
모든 부모_노드들에 대하여

    hepify(부모_노드):
        큰_자식 := max(왼쪽_자식, 오른쪽_자식)
        if(큰_자식 > 부모_노드)
            swap(큰_자식, 부모_노드)
            heapify(큰_자식)

재귀로 구현된 heapify()가 등장하는데, 이 함수가 하는 역할은 주어진 node를 부모로 시작해서 단말 node로 내려가면서 max heap 조건에 맞도록 변경해 주는 역할을 한다. heapify()는 큰 자식과 부모를 swap() 하는 경우 재귀하므로 시간 복잡도는 O(트리높이)가 된다.

Heap tree를 생성하는 방법을 고민해 본 적이 있다면, 부모 node들을 순회 할 때 역순으로 순회하는게 얼마나 영리한 방법인지 무릎을 쳤을 것이다. 내 얘기다;;

예제

임의의 정렬되지 않은 배열 { 2, 7, 5, 4, 1, 6, 10, 3, 9, 8}을 예로들어 보자. 10개의 node를 가지는 tree를 배열로 구현 할 때, 부모 node들의 index는 소숫점_버림(N/2) – 1로 계산할 수 있다. 따라서 10개의 node를 가지는 이 tree의 부모 node들의 위치는 [0], [1], [2], [3], [4]이다. (C/C++로 구현 할때는 N/2한 값을 그냥 int형 변수에 넣으면 된다)

각 부모 node들과 자식 node들을 subtree라고 하면 이 예제는 다음과 같이 5개의 subtree들로 구분될 수 있다.

Heapify – Subtree A

부모인 4번째 index의 값과 하나 밖에 없는 자식인 9번째 index의 값을 비교한다. 자식의 값이 더 크므로 부모와 swap()한다.

Heapify – Subtree B

부모인 3번째 index와 왼쪽 자식인 7번째, 오른쪽 자식인 8번째를 비교해서 가장 큰 오른쪽 자식과 부모 node를 swap()한다.

Heapify – Subtree C

오른쪽 자식인 index 6번과 부모인 index 2번을 교체한다.

Heapify – Subtree D

1번 index의 왼쪽 자식이 더 크므로 부모와 swap()한다.

Heapify – Subtree E

2번 index의 값이 더 커서 부모인 0번 index와 swap()하고 보니 2번 index를 부모로 하는 subtree가 더이상 max heap이 아니게 된다.

그래서 다시 한번 heapify()를 호출해서 max heap을 만든다.

Code

/*
  Name: buildHeapTree
  Desc.: Makes sure all sub-trees to be max heapified.
  Args.:
    - arr : Pointer to array to be sorted.
    - arrSize : Size of the array.
*/
static void buildHeapTree(int* arr, int arrSize)
{
    int parentIdx = (arrSize / 2) - 1;
    int arrayLastIdx = arrSize - 1;
 
    for(; parentIdx >= 0; parentIdx--)
    {
        maxHeapify(arr, arrayLastIdx, parentIdx);
    }
}

/*
  Name: swap
  Desc.: Exchanges two elements of the array 'arr' that two given indices indicates.
  Args.:
    - arr: Pointer to array to be sorted.
    - idx1, idx2 : Two indices to be swapped.
*/
static void swap(int* arr, int idx1, int idx2)
{
    int t = std::move(arr[idx1]);
    arr[idx1] = std::move(arr[idx2]);
    arr[idx2] = std::move(t);
}

 
/*
  Name: maxHeapify
  Desc.: Makes given tree and it's sub-trees to be max heap trees.
  Args:
    - arr : Pointer to array to be sorted.
    - arrayLastIdx : Last index of the given array.
    - parentIdx : Index of the parent node of the tree.
*/
static void maxHeapify(int* arr, int arrayLastIdx, int parentIdx)
{
    int lcIdx = (parentIdx * 2) + 1;  // Index for left child node.
    int rcIdx = lcIdx + 1;            // Index for right child node.
    int biggerChildIdx = lcIdx;       // Index for child that has bigger value.
 
    // Stop recursion if left child index exceeds last index of the array.
    if(lcIdx > arrayLastIdx)
        return;
 
    // Left child would be the only one if there's no right child. 
    if(rcIdx > arrayLastIdx)
        biggerChildIdx = lcIdx;
    else   // Which of left/right is bigger if both are exits?
        biggerChildIdx = (arr[lcIdx] < arr[rcIdx]) ? rcIdx : lcIdx;
 
    // Swap and heapify if child is bigger than parent.
    if(arr[parentIdx] < arr[biggerChildIdx])
    {
        swap(arr, parentIdx, biggerChildIdx);
        maxHeapify(arr, arrayLastIdx, biggerChildIdx);
    }
 
    return;
}