LeetCode Grinding
Data Structures1 menit baca

Pengenalan Priority Queue

Priority queue memilih item berikutnya berdasarkan prioritas, dengan heap sebagai implementasi yang umum.

Di artikel ini 3 bagian

Kadang item harus diproses berdasarkan prioritas, bukan waktu kedatangannya. Priority queue mengeluarkan item dengan prioritas tertinggi di setiap removal, sedangkan queue biasa selalu mengeluarkan item yang paling lama.

Urutan berdasarkan prioritas

Minimum priority queue mengembalikan nilai prioritas terkecil lebih dulu; maximum priority queue mengembalikan yang terbesar. Aku membandingkan scan array dengan heap untuk urutan ini.

Implementasi array dan heap

Versi array menyimpan setiap item, lalu mencari prioritas terkecil setiap kali dequeue:

javascript
class PriorityQueueArray {
  constructor() {
    this.queue = [];
  }

  enqueue(item, priority) {
    this.queue.push({ item, priority });
  }

  dequeue() {
    if (this.isEmpty()) return null;

    // Find highest priority (lowest number for min-priority)
    let highestPriorityIndex = 0;
    for (let i = 1; i < this.queue.length; i++) {
      if (this.queue[i].priority < this.queue[highestPriorityIndex].priority) {
        highestPriorityIndex = i;
      }
    }
    return this.queue.splice(highestPriorityIndex, 1)[0];
  }

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

dequeue butuh O(n) waktu karena menelusuri array lalu menghapus satu elemen.

Versi heap menjaga prioritas terkecil tetap di root. Insertion menggeser item baru ke atas, dan removal menggeser root pengganti ke bawah. Kedua operasi butuh O(log n):

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

  enqueue(item, priority) {
    this.heap.push({ item, priority });
    this.bubbleUp(); // Maintain heap property
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[index].priority >= this.heap[parentIndex].priority) break;

      // Swap with parent
      [this.heap[index], this.heap[parentIndex]] = [
        this.heap[parentIndex],
        this.heap[index],
      ];
      index = parentIndex;
    }
  }

  dequeue() {
    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();
    this.sinkDown(0); // Maintain heap property
    return root;
  }

  sinkDown(index) {
    const length = this.heap.length;
    const element = this.heap[index];

    while (true) {
      const leftIndex = 2 * index + 1;
      const rightIndex = 2 * index + 2;
      let swapIndex = null;

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

      if (
        rightIndex < length &&
        this.heap[rightIndex].priority <
          (swapIndex === null
            ? element.priority
            : this.heap[leftIndex].priority)
      ) {
        swapIndex = rightIndex;
      }

      if (swapIndex === null) break;

      [this.heap[index], this.heap[swapIndex]] = [
        this.heap[swapIndex],
        this.heap[index],
      ];
      index = swapIndex;
    }
  }

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

Kompleksitas dan pemakaian umum

Menurut aku priority queue berguna untuk algoritma shortest path Dijkstra, penjadwalan task, simulasi event, dan menggabungkan k sorted list. Tiap kasus itu berulang kali butuh item terkecil atau terbesar yang tersisa.

Versi array butuh waktu removal O(n) dan storage O(n). Versi heap menjaga operasi enqueue dan dequeue tetap O(log n), dengan storage O(n). Heap menambah kerja implementasi, tapi menghindari scan setiap item di setiap removal.

Untuk removal yang berulang, aku pakai heap supaya nggak mencari di seluruh koleksi setiap kali. Scan array masih bisa dipertimbangkan kalau queue-nya kecil.

Topik

Makasih udah baca

Gimana menurutmu?

Kasih reaksi atau komentar di bawah.

Memuat reaksi…

Bagikan tulisan ini

Memuat komentar...

Tulisan terkait

Semua tulisan