Heap의 정의와 kotlin 구현

정의

힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성(property)을 만족한다.

• A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다.

힙에는 두가지 종류가 있으며, 부모노드의 키값이 자식노드의 키 값보다 항상 큰 힙을 '최대 힙(max_heap)', 부모노드의 키 값이 자식노드의 키 값보다 항상 작은 힙을 '최소 힙(min_heap)'이라고 부른다.

 

키 값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않는다.

 

각 노드의 자식노드의 최대개수는 힙의 종류에 따라 다르지만, 대부분의 경우는 자식노드의 개수가 최대 2개인 이진 힙(binary heap)을 사용한다. 힙에서는 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 뿌리노드에 오게 되는 특징이 있으며, 이를 응용하면 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다.

 

구현

완전이진트리를 배열로 표현해 보자.

val tree = arrayListOf('a', 'b', 'c', 'd', 'e', null, null)

 

- 트리의 높이가 h이면, 크기 2^h의 크기의 배열을 생성

- index 0은 root node를 담는다.

index k 이면

tree[ 2*k + 1 ]은 tree[k]의 왼쪽 자식 노드

tree[ 2*k + 2 ]은 tree[k]의 왼쪽 자식 노드

- 자식이 없으면 null 로 처리한다.

 

임의 n에 대하여, 

* tree[n]의 부모노드는 tree[ (n-1) / 2 ]가 성립한다. 

* 완전이진트리(complete binary tree)를 기본으로 하는 자료구조이기 때문에 { root a, null, c, d, null, f } 중간에 null올 수 없다.

 

 

make_heap ()

 - heap 속성을 만족 하기 위해, A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립하도록 노드의 위치를 변경하는 함수

 

위 그림의 완전 이진트리를 배열로 표현하게 되면 아래 코드와 같지만, heap 속성을 만족하지는 못합니다.

val tree = arrayListOf(2, 8, 6, 1, 10, 15, 3, 12, 11, null, null, null, null, null, null)

 

code

    /*
        배열이 heap 성질을 만족하도록
        마지막 노드에서 부터 순회하면서 힙성질을 만들어 올라온다. 
     */
    fun makeHeap() {
        val end = tree.indexOfLast { it != null }
        for (i in end downTo 0) {
            if (isLeaf(i)) continue
            heapifyDown(i)
        }
    }

    /*
        해당 노드가 Leaf node 인지 확인한다. 
     */
    private fun isLeaf(idx: Int): Boolean =
        getChild(idx, 'L') == null && getChild(idx, 'R') == null

    /*
        옵션에 따라 해당 노드의 자식의 값을 가지고 온다. 
     */
    private fun getChild(idx: Int, option: Char): Int? {

        val dir = if (option == 'L') 1 else 2

        return try {
            tree[(idx * 2) + dir]
        } catch (e: IndexOutOfBoundsException) {
            null
        }
    }

    /*
        가장 최소 형태의 root left right 중 힙성질을 만족하도록 
        1. 두 자식을 먼저 비교
        2. root와 더 큰 자식을 비교 
     */
    private fun heapifyDown(idx: Int) {
        var i = idx
        while (!isLeaf(i)) {
            val left = getChild(i, 'L') ?: -1
            val right = getChild(i, 'R') ?: -1

            val tempIdx = if (left > right) (2 * i) + 1 else (2 * i) + 2

            val maxIdx =
                if (tempIdx == (2 * i) + 1) {
                    if (tree[i]!! > left) i else (2 * i) + 1
                } else {
                    if (tree[i]!! > right) i else (2 * i) + 2
                }

            if (i != maxIdx){
                swap(i, maxIdx)
                i = maxIdx
            }else{
                break
            }
        }
    }

    private fun swap(a: Int, b: Int) {
        val temp = tree[a]
        tree[a] = tree[b]
        tree[b] = temp
    }

 

*make_heap() 연산은 O(n)의 시간복잡도를 가지며 수학적 증명은 이 글에서는 생략한다. 

 

insert()

    /*
        새로운 값이 들어오면 heap 성질에 맞도록 알맞은 위치에 데이터를 저장한다.
     */
    fun insert(num: Int) {
        // 배열의 공간 확인 및 reSize
        if (tree.isEmpty() || tree[tree.lastIndex] != null)
            resize()

        // leaf node에 삽입.
        val emptyIdx = tree.indexOfFirst { it == null }
        tree[emptyIdx] = num
        heapifyUp(emptyIdx)
    }

    /*
        tree의 크기를 2배로 증가시킨다.
   */
    private fun resize() {
        val temp = Array<Int?>((tree.size + 1) * 2 + 1) { null }
        for (i in 0 until tree.size){
            temp[i] = tree[i]
        }
        tree = temp
    }

    /*
        정해진 idx에서 root 까지 부모 노드와 비교하여 위치를 변경한다.
        O(logN)
     */
    private fun heapifyUp(idx: Int) {
        var temp = idx
        // root node idx는 0이다.
        while (temp > 0 && tree[(temp - 1) / 2]!! < tree[temp]!!) {
            swap((temp - 1) / 2, temp)
            temp = (temp - 1) / 2
        }
    }

 

 

find_max() & delete_max()

    /*
        Root인 가장 큰값을 반환한다.
     */
    fun findMax() = tree.first()

    /*
        root idx를 비워서 지우고,
        가장 큰 값의 root와  마지막 leaf node와 값을 교환후
        heapifyDown으로 heap 성질은 만족 시킨다. 
     */
    fun deleteMax(): Int{

        if (tree.isEmpty()) return -1

        val maxValue = tree[0]!!
        tree[0] = null
        swap(0,  tree.indexOfLast { it != null })

        heapifyDown(0)
        return maxValue
    }

 

전체코드 

import kotlin.math.pow


class MaxHeap(vararg args: Int) {

    var tree = Array<Int?>(calTreeSize(args.size)) { null }

    init {
        for (i in 0 until args.size) {
            tree[i] = args[i]
        }
        makeHeap()
    }

    private fun calTreeSize(arrSize: Int): Int = 2.0.pow(calculateHeight(arrSize).toDouble()).toInt() - 1

    private fun calculateHeight(size: Int): Int {

        var h = 0
        var temp = size

        while (temp > 0) {
            temp /= 2
            h += 1
        }

        return h
    }

    /*
        배열이 heap 성질을 만족하도록
        마지막 노드에서 부터 순회하면서 힙성질을 만들어 올라온다.
     */
    fun makeHeap() {
        val end = tree.indexOfLast { it != null }
        for (i in end downTo 0) {
            if (isLeaf(i)) continue
            heapifyDown(i)
        }
    }

    /*
        해당 노드가 Leaf node 인지 확인한다.
     */
    private fun isLeaf(idx: Int): Boolean =
        getChild(idx, 'L') == null && getChild(idx, 'R') == null

    /*
        옵션에 따라 해당 노드의 자식의 값을 가지고 온다.
     */
    private fun getChild(idx: Int, option: Char): Int? {

        val dir = if (option == 'L') 1 else 2

        return try {
            tree[(idx * 2) + dir]
        } catch (e: IndexOutOfBoundsException) {
            null
        }
    }

    /*
        가장 최소 형태의 root left right 중 힙성질을 만족하도록
        1. 두 자식을 먼저 비교
        2. root와 더 큰 자식을 비교
     */
    private fun heapifyDown(idx: Int) {
        var i = idx
        while (!isLeaf(i)) {
            val left = getChild(i, 'L') ?: -1
            val right = getChild(i, 'R') ?: -1

            val tempIdx = if (left > right) (2 * i) + 1 else (2 * i) + 2

            val maxIdx =
                if (tempIdx == (2 * i) + 1) {
                    if (tree[i]!! > left) i else (2 * i) + 1
                } else {
                    if (tree[i]!! > right) i else (2 * i) + 2
                }

            if (i != maxIdx) {
                swap(i, maxIdx)
                i = maxIdx
            } else {
                break
            }
        }
    }

    private fun swap(a: Int, b: Int) {
        val temp = tree[a]
        tree[a] = tree[b]
        tree[b] = temp
    }

    /*
        새로운 값이 들어오면 heap 성질에 맞도록 알맞은 위치에 데이터를 저장한다.
     */
    fun insert(num: Int) {
        // 배열의 공간 확인 및 reSize
        if (tree.isEmpty() || tree[tree.lastIndex] != null)
            resize()

        // leaf node에 삽입.
        val emptyIdx = tree.indexOfFirst { it == null }
        tree[emptyIdx] = num
        heapifyUp(emptyIdx)
    }

    /*
        tree의 크기를 2배로 증가시킨다.
   */
    private fun resize() {
        val temp = Array<Int?>((tree.size + 1) * 2 + 1) { null }
        for (i in 0 until tree.size){
            temp[i] = tree[i]
        }
        tree = temp
    }

    /*
        정해진 idx에서 root 까지 부모 노드와 비교하여 위치를 변경한다.
        O(logN)
     */
    private fun heapifyUp(idx: Int) {
        var temp = idx
        // root node idx는 0이다.
        while (temp > 0 && tree[(temp - 1) / 2]!! < tree[temp]!!) {
            swap((temp - 1) / 2, temp)
            temp = (temp - 1) / 2
        }
    }

    /*
        Root인 가장 큰값을 반환한다.
     */
    fun findMax() = tree.first()

    /*
        root idx를 비워서 지우고,
        가장 큰 값의 root와  마지막 leaf node와 값을 교환후
        heapifyDown으로 heap 성질은 만족 시킨다.
     */
    fun deleteMax(): Int{

        if (tree.isEmpty()) return -1

        val maxValue = tree[0]!!
        tree[0] = null
        swap(0,  tree.indexOfLast { it != null })

        heapifyDown(0)
        return maxValue
    }

}

fun main() {

    val heap = MaxHeap(2, 8, 6, 1, 10, 15, 3, 12, 11)
    println(heap.tree.joinToString(" "))

    heap.insert(14)
    println(heap.tree.joinToString(" "))

    heap.findMax()
    heap.deleteMax()
    println(heap.tree.joinToString(" "))
}

 

시간복잡도

 

make_heap() O(n)

insert() O(logn)

findMax() O(1)

deleteMax() O(logn)