[Data Structure] Heap

ツリーベースのデータ構造であり、heap属性を満たす完全な二叉木である.

実施方法

ArrayのIndexを使用してアクセスする方法
ノードを作成してノードにアクセスする方法があります

Insert

Arrayを使用する場合は、最後に入れ、heapifyプロセス(下から上へ)を経ます.

Delete

Arrayを使用すると、最初のインデックス値と最後のインデックス値が変更されます.
最後の値を除いて値を得る
その後heapifyプロセス(toptobottom)を経験します

時間の複雑さ

参考資料

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」を乗じて値を加算したり、記号を変えたりすればいいです