Bagaimana cara Anda mengimplementasikan stable bounded priority queue?

1. Masalah

Implementasikan StableBoundedPriorityQueue. Setiap entri memiliki priority, sequence, dan value; bandingkan priority terlebih dahulu dan sequence kedua. Dengan kapasitas C, push menyimpan paling banyak C entri. Entri baru menggantikan entri terburuk saat ini hanya jika entri tersebut lebih baik; jika tidak, entri tersebut ditolak. pop mengembalikan entri terbaik.

2. Batasan dan klarifikasi

• C adalah bilangan bulat positif; dengan C=0, setiap penyisipan ditolak tanpa menyentuh batas array.
• Angka yang lebih rendah berarti prioritas lebih tinggi; prioritas yang sama harus keluar sesuai urutan penyisipan.
• Menolak item terburuk saat penuh memerlukan pencarian item tersebut. Min-heap tunggal tidak dapat mengeksposnya secara langsung dalam O(log C), jadi gunakan indeks kedua, max-heap, atau terima pemindaian linear (linear scan).
• Mulailah dengan implementasi berulir tunggal (single-threaded). Produsen dan konsumen bersamaan memerlukan kunci eksternal atau antrean konkuren khusus.

3. Pendekatan inti

Gunakan min-heap untuk item berikutnya, yang diurutkan berdasarkan (priority, sequence). Gunakan max-heap untuk item terburuk, yang diurutkan sedemikian rupa sehingga prioritas yang lebih besar dan urutan yang lebih baru dianggap lebih buruk. Kedua heap merujuk ke rekaman entri yang sama. Penghapusan menandai suatu entri alive=false; setiap heap membuang node mati saat mereka mencapai akarnya. Penghapusan tertunda (lazy deletion) ini menghindari penghapusan heap pada posisi sembarang.

Untuk kapasitas kecil, pemindaian linear untuk item terburuk lebih sederhana: pop tetap O(log C), sedangkan push pada antrean penuh memakan biaya O(C). Sampaikan trade-off ini sebelum menyajikan pengoptimalan dua heap.

4. Implementasi referensi

record Entry(priority, sequence, value, alive=true)

push(priority, value):
  if capacity == 0: return false
  candidate = Entry(priority, nextSequence(), value)
  if size < capacity:
    add candidate to minHeap and maxHeap
    size += 1
    return true
  discard dead nodes from maxHeap
  worst = maxHeap.peek()
  if (priority, candidate.sequence) >= (worst.priority, worst.sequence):
    return false
  worst.alive = false
  pop maxHeap
  add candidate to both heaps
  return true

pop():
  discard dead nodes from minHeap
  if minHeap is empty: return EMPTY
  entry = pop minHeap
  entry.alive = false
  size -= 1
  return entry.value

Kunci max-heap berarti "lebih besar lebih buruk": prioritas yang lebih besar lebih buruk, dan untuk prioritas yang sama urutan yang lebih besar datang belakangan dan oleh karena itu lebih buruk. Jika suatu bahasa tidak memiliki max-heap, buat kuncinya negatif atau sediakan pembanding (comparator). nextSequence harus monotonik; gunakan integer lebar atau setel ulang hanya ketika antrean kosong.

5. Kompleksitas dan trade-off

Penyisipan yang diterima menambahkan satu node ke setiap heap, sehingga memakan biaya O(log C); pop memakan biaya O(log C). Penggantian juga memakan biaya O(log C). Penghapusan tertunda dapat meninggalkan node mati untuk sementara, tetapi setiap node mati di-pop satu kali, memberikan operasi teramortisasi O(log C) dan ruang O(C) dengan peningkatan faktor konstan. Varian pemindaian linear menggunakan lebih sedikit ruang dan kode yang lebih pendek tetapi berbiaya O(C) untuk penyisipan antrean penuh.

6. Verifikasi dan observabilitas

• Cakup C=0, C=1, antrean kosong, penolakan berulang, dan penggantian berulang.
• Sisipkan beberapa entri berprioritas sama dan verifikasi urutan FIFO berdasarkan urutan (sequence).
• Uji kandidat yang lebih buruk, sama, dan lebih baik terhadap antrean yang penuh; harapkan tolak, tolak, dan ganti.
• Bandingkan jejak operasi acak dengan model referensi yang mengurutkan semua entri hidup berdasarkan (priority, sequence) dan memotongnya ke C.
• Catat panjang antrean, jumlah penolakan, dan jumlah pembersihan node mati. Tingkat penolakan yang meningkat dapat memicu pembatasan laju (throttling) atau pembuangan beban (load shedding) di sisi hulu.

7. Kesalahan umum

• Hanya mengurutkan berdasarkan prioritas, yang menghilangkan stabilitas FIFO ketika terjadi seri.
• Mengasumsikan prioritas numerik yang lebih besar lebih penting tanpa mengonfirmasi arahnya.
• Melakukan pop pada akar heap sebelum penerimaan, yang membuang tugas terbaik saat antrean penuh.
• Gagal membuang node mati, sehingga peek mengembalikan entri yang sudah diganti atau dibatalkan.
• Menggunakan stempel waktu jam dinding (wall-clock timestamps) untuk nomor urut; pemunduran jam atau penyisipan pada tick yang sama dapat merusak FIFO.

8. Pertanyaan lanjutan

Bagaimana cara Anda menerapkan kuota per-tenant?

Simpan hitungan dan batas untuk setiap tenant. Periksa kapasitas global dan kuota tenant sebelum penyisipan, dan hitung kedua alasan penolakan secara terpisah agar tenant yang padat terlihat.

Bagaimana cara Anda membatalkan atau mengubah prioritas suatu entri?

Berikan setiap entri sebuah ID dan gunakan penghapusan tertunda. Pembatalan menandainya sebagai mati; perubahan prioritas membuat entri baru dan membatalkan entri lama. Bersihkan node mati saat melakukan peek atau pop alih-alih menghapus posisi heap sembarang.

Kapan sebaiknya Anda menggunakan concurrent priority queue dari pustaka?

Gunakan implementasi konkuren yang teruji ketika beberapa thread atau proses memproduksi dan mengonsumsi, penantian pemblokiran (blocking waits) diperlukan, atau batas memori sangat ketat. Desain dua heap kustom hanya tepat digunakan dengan batasan berulir tunggal yang jelas dan siklus hidup yang dapat diuji.