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:
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):
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.

Memuat komentar...