[백준] 1927번 최소힙, 11279번 최대힙

1927번 최소힙
11279번 최대힙

접근방법

heap 구현을 직접하여 풀이하였다.
heap 내부는 node를 이용하는 Tree구조가 아닌 Array를 이용하여 문제를 풀었다.

자식 노드와 부모 노드의 인덱스 관계식을 얻어서 siftUp/Down 함수를 만들었고
해당 함수를 사용하는 insert, remove함수를 만들었다.

최소힙과 최대힙은 코드의 부등호를 바꾸거나 최대힙의 경우 주어진 숫자에 '-1'을 곱하여 넣은 후 꺼낼 때 부호를 바꿔주는 방식으로 문제를 풀 수 있다.

시간복잡도

삽입: O(h) heapify 고려 (h: 높이)
삭제: O(h) heapify 고려 (h: 높이)
전체 시간복잡도: O(nlogn)

Code

import java.io.BufferedReader
import java.io.InputStreamReader
import java.io.BufferedWriter
import java.io.OutputStreamWriter

class IO {
    private val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    fun getInt(): Int {
        return br.readLine().toInt()
    }
   
}

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
            }
        }
    }
}

fun main() {
    val io = IO()
    val heap = MinHeap()
    val numList = mutableListOf<Int>()
    repeat(io.getInt()) {
        numList.add(io.getInt())
    }
    numList.forEach { num ->
        if (num == 0) {
            io.bw.write(heap.remove().toString() + "\n")
        } else {
            heap.insert(num)
        }
    }
    io.bw.flush()
    io.bw.close()
}