[Data Structure] Heap

트리를 기반으로 둔 자료구조이고 heap의 속성을 만족시키는 complete binary tree이다.

구현 방법

Array의 Index를 이용해서 접근하는 방법
Node를 만들어서 접근하는 방법이 존재

Insert

Array 이용시 마지막에 넣어준 후 heapify 과정을 거친다 (bottom to top)

Delete

Array 이용 시 제일 처음의 인덱스 값과 마지막 값을 바꾼다
마지막 값을 제거하며 값을 얻는다
이후 heapify 과정을 거친다 (top to bottom)

시간복잡도

참고자료

Code

class MinHeap {
    val arr = ArrayList<Int>()

    fun insert(element: Int) {
        arr.add(element)
        var nowIdx = arr.lastIndex
        siftUp(nowIdx)
    }

    private fun siftUp(idx: Int) {
        var tmpIdx = idx
        while (tmpIdx > 0 ) {
            val parentIdx = (tmpIdx -1) / 2
            if (arr[parentIdx] < arr[tmpIdx]) {
                break
            } else {
                val tmp = arr[parentIdx]
                arr[parentIdx] = arr[tmpIdx]
                arr[tmpIdx] = tmp
                tmpIdx = parentIdx
            }
        }
    }

    fun remove(): Int {
        if (arr.size == 0) {
            return 0
        }
        var nowIdx = 0
        val tmp = arr.last()
        arr[arr.lastIndex] = arr[0]
        arr[0] = tmp
        val ret = arr.removeAt(arr.lastIndex)
        siftDown(nowIdx)
        return ret
    }

    private fun siftDown(idx: Int) {
        var tmpIdx = idx
        while (tmpIdx < arr.size) {
            val left = 2 * tmpIdx + 1
            val right = left + 1
            var candidate = arr[tmpIdx]
            var cIdx = tmpIdx
            if (left <= arr.lastIndex && arr[left] < arr[tmpIdx]) {
                cIdx = left
                candidate = arr[left]
            }
            if (right <= arr.lastIndex && arr[right] < candidate) {
                cIdx = right
                candidate = arr[right]
            }
            if (tmpIdx == cIdx) {
                break
            } else {
                arr[cIdx] = arr[tmpIdx]
                arr[tmpIdx] = candidate
                tmpIdx = cIdx
            }
        }
    }
}

maxHeap은 넣으려는 숫자에 '-1'을 곱해 값을 넣거나, 부등호를 바꾸어주면 된다