LeetCode Grinding
Data Structures2 menit baca

Memahami Priority Queue (Min-Heap)

Membangun min heap dan memakainya untuk memasukkan item dan mengambil item terkecil berdasarkan prioritas.

Di artikel ini 5 bagian

Aku udah memakai priority queue sebelum membuat implementasinya sendiri. Membuat min heap ini membantuku mengikuti perubahan saat penambahan atau penghapusan merusak urutan antara parent dan child-nya.

Apa Itu Min Heap?

Min heap adalah binary tree yang:

  • Parent-nya selalu lebih kecil atau sama dengan child-nya
  • Root-nya adalah elemen terkecil
  • Bentuknya complete binary tree (diisi dari kiri ke kanan)

Struktur ini bikin aku bisa ambil elemen minimum dalam O(1) dan menghapusnya dalam O(log n).

Implementasi Min Heap Aku

Array menyimpan tree dari kiri ke kanan, satu level setiap urutan. Perhitungan index di bawah mencari parent dan child sebuah node.

javascript
class MinHeap {
    constructor() {
        this.heap = [];
    }

    // Helper methods to navigate the tree
    getParentIndex(i) { 
        return Math.floor((i - 1) / 2); 
    }
    
    getLeftChildIndex(i) { 
        return 2 * i + 1; 
    }
    
    getRightChildIndex(i) { 
        return 2 * i + 2; 
    }

    // Add element to heap
    add(value) {
        this.heap.push(value);
        this.heapifyUp(); // Maintain heap property
    }

    // Remove and return minimum element
    poll() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) {
            return this.heap.pop();
        }

        const root = this.heap[0];
        this.heap[0] = this.heap.pop(); // Move last element to root
        this.heapifyDown(); // Maintain heap property
        return root;
    }

    // Move element up to maintain heap property
    heapifyUp() {
        let index = this.heap.length - 1;
        
        while (index > 0) {
            const parentIndex = this.getParentIndex(index);
            
            // If parent is smaller or equal, we're done
            if (this.heap[parentIndex] <= this.heap[index]) {
                break;
            }
            
            // Swap with parent
            [this.heap[index], this.heap[parentIndex]] = 
            [this.heap[parentIndex], this.heap[index]];
            index = parentIndex;
        }
    }

    // Move element down to maintain heap property
    heapifyDown() {
        let index = 0;
        
        while (this.getLeftChildIndex(index) < this.heap.length) {
            const leftIndex = this.getLeftChildIndex(index);
            const rightIndex = this.getRightChildIndex(index);
            let smallerChildIndex = leftIndex;

            // Find smaller child
            if (rightIndex < this.heap.length && 
                this.heap[rightIndex] < this.heap[leftIndex]) {
                smallerChildIndex = rightIndex;
            }

            // If current is smaller than both children, we're done
            if (this.heap[index] <= this.heap[smallerChildIndex]) {
                break;
            }

            // Swap with smaller child
            [this.heap[index], this.heap[smallerChildIndex]] = 
            [this.heap[smallerChildIndex], this.heap[index]];
            index = smallerChildIndex;
        }
    }

    isEmpty() {
        return this.heap.length === 0;
    }
}

Cara Kerjanya

Menambahkan elemen:

  1. Tambahkan ke ujung array
  2. "Bubble up" dengan membandingkannya ke parent
  3. Tukar kalau parent lebih besar
  4. Ulangi sampai heap property kembali terpenuhi

Menghapus minimum:

  1. Hapus root (minimum)
  2. Pindahkan elemen terakhir ke root
  3. "Bubble down" dengan membandingkannya ke child
  4. Tukar dengan child yang lebih kecil kalau perlu
  5. Ulangi sampai heap property kembali terpenuhi
javascript
const minHeap = new MinHeap();
minHeap.add(10);
minHeap.add(5);
minHeap.add(20);
minHeap.add(1);

while (!minHeap.isEmpty()) {
    console.log(minHeap.poll()); // Prints: 1, 5, 10, 20
}

PriorityQueue Bawaan Java

Di Java, aku bisa pakai PriorityQueue bawaan, yang secara default adalah min heap:

java
import java.util.PriorityQueue;

public class MinHeapExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        minHeap.add(10);
        minHeap.add(5);
        minHeap.add(20);
        minHeap.add(1);
        
        while (!minHeap.isEmpty()) {
            System.out.println(minHeap.poll()); // Prints: 1, 5, 10, 20
        }
    }
}

Biaya memperbaiki heap

Penambahan bisa bergerak dari level terakhir ke root. Penghapusan bisa bergerak dari root ke level terakhir. Complete binary tree punya O(log n) level, jadi setiap perbaikan butuh O(log n) waktu. Array-nya memakai O(n) space.

Membaca nilai minimum cuma perlu root, jadi butuh O(1) waktu. Sisa array nggak sepenuhnya terurut; yang dijamin cuma urutan antara setiap parent dan child-nya.

Topik

Makasih udah baca

Gimana menurutmu?

Kasih reaksi atau komentar di bawah.

Memuat reaksi…

Bagikan tulisan ini

Memuat komentar...

Tulisan terkait

Semua tulisan