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
Removal mengembalikan item dengan prioritas tertinggi di antara item yang sedang ada di queue. Minimum priority queue mengembalikan value terkecil lebih dulu. Maximum priority queue mengembalikan value terbesar lebih dulu. Saya butuh urutan ini waktu menjadwalkan task, karena FIFO queue selalu mengeluarkan item yang paling lama. Saya membandingkan scan array dengan heap.
Implementasi array dan heap
Implementasi array pertama saya menyimpan setiap item dan mencari prioritas terkecil di setiap 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;
}
}
Versi array ini gampang dipahami, tapi dequeue jadi O(n) karena dia men-scan 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;
}
}
enqueue dan dequeue sama-sama O(log n) di implementasi ini.
Kompleksitas dan pemakaian umum
Menurut saya 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.
Priority queue bikin aturan urutannya jadi eksplisit. Pilih min heap atau max heap sesuai prioritas yang dibutuhkan, lalu pakai heap kalau removal yang berulang harus tetap logaritmik.
Memuat komentar...