Heap dan Priority Queue

// Demo Heap dan Priority Queue: min-heap implementation + java.util.PriorityQueue.

// === Min-Heap implementation ===
class MinHeap {
    private val data = mutableListOf<Int>()

    fun size(): Int = data.size
    fun isEmpty(): Boolean = data.isEmpty()

    fun peek(): Int? = data.firstOrNull()

    // Insert: tambah di akhir, lalu sift-up
    fun insert(value: Int) {
        data.add(value)
        siftUp(data.lastIndex)
    }

    private fun siftUp(idx: Int) {
        var i = idx
        while (i > 0) {
            val parent = (i - 1) / 2
            if (data[i] < data[parent]) {
                val t = data[i]; data[i] = data[parent]; data[parent] = t
                i = parent
            } else break
        }
    }

    // Extract min: ambil root, pindahkan elemen terakhir ke root, lalu sift-down
    fun extractMin(): Int? {
        if (data.isEmpty()) return null
        val min = data[0]
        val last = data.removeAt(data.lastIndex)
        if (data.isNotEmpty()) {
            data[0] = last
            siftDown(0)
        }
        return min
    }

    private fun siftDown(idx: Int) {
        var i = idx
        val n = data.size
        while (true) {
            val left = 2 * i + 1
            val right = 2 * i + 2
            var smallest = i
            if (left < n && data[left] < data[smallest]) smallest = left
            if (right < n && data[right] < data[smallest]) smallest = right
            if (smallest != i) {
                val t = data[i]; data[i] = data[smallest]; data[smallest] = t
                i = smallest
            } else break
        }
    }

    fun toList(): List<Int> = data.toList()
}

// === Top-K via min-heap ===
fun topKLargest(arr: IntArray, k: Int): List<Int> {
    val minHeap = MinHeap()
    for (x in arr) {
        if (minHeap.size() < k) {
            minHeap.insert(x)
        } else if (minHeap.peek()!! < x) {
            minHeap.extractMin()
            minHeap.insert(x)
        }
    }
    // K elemen terbesar ada di heap, urutkan descending
    val result = mutableListOf<Int>()
    while (!minHeap.isEmpty()) result.add(minHeap.extractMin()!!)
    return result.reversed()
}

fun main() {
    println("=== Demo Heap dan Priority Queue ===")

    println("--- Min-Heap manual ---")
    val heap = MinHeap()
    listOf(10, 5, 20, 3, 8, 15, 1).forEach { heap.insert(it) }
    println("Heap internal array: ${heap.toList()}")
    println("Peek (min): ${heap.peek()}")

    println("Extract min berurutan:")
    val sorted = mutableListOf<Int>()
    while (!heap.isEmpty()) sorted.add(heap.extractMin()!!)
    println("Hasil extract: $sorted")

    println()
    println("--- java.util.PriorityQueue ---")
    val pq = java.util.PriorityQueue<Int>()
    listOf(10, 5, 20, 3, 8, 15, 1).forEach { pq.add(it) }
    println("Poll berurutan (min-heap default):")
    val pqSorted = mutableListOf<Int>()
    while (pq.isNotEmpty()) pqSorted.add(pq.poll())
    println("$pqSorted")

    println()
    println("--- Max-heap via reverseOrder ---")
    val maxPq = java.util.PriorityQueue<Int>(java.util.Collections.reverseOrder())
    listOf(10, 5, 20, 3, 8, 15, 1).forEach { maxPq.add(it) }
    val maxSorted = mutableListOf<Int>()
    while (maxPq.isNotEmpty()) maxSorted.add(maxPq.poll())
    println("Poll (max-heap): $maxSorted")

    println()
    println("--- Top-K elemen terbesar ---")
    val data = intArrayOf(4, 10, 8, 3, 15, 7, 20, 1, 12, 9)
    println("Data: ${data.toList()}")
    println("Top 3 terbesar: ${topKLargest(data, 3)}")
    println("Top 5 terbesar: ${topKLargest(data, 5)}")
}

=== Demo Heap dan Priority Queue ===
--- Min-Heap manual ---
Heap internal array: [1, 5, 3, 10, 8, 20, 15]
Peek (min): 1
Extract min berurutan:
Hasil extract: [1, 3, 5, 8, 10, 15, 20]

--- java.util.PriorityQueue ---
Poll berurutan (min-heap default):
[1, 3, 5, 8, 10, 15, 20]

--- Max-heap via reverseOrder ---
Poll (max-heap): [20, 15, 10, 8, 5, 3, 1]

--- Top-K elemen terbesar ---
Data: [4, 10, 8, 3, 15, 7, 20, 1, 12, 9]
Top 3 terbesar: [20, 15, 12]
Top 5 terbesar: [20, 15, 12, 10, 9]