Priority queue (PQ) – huddi stack va queue kabi ma’lumotlar to’plami. Yagona farqi – qaysi element o’chirilishida. Stack’da ohirgi qo’shilgan element birinchi bo’lib o’chirilsa, queue’da birinchi qo’shilgan element birinchi o’chiriladi. PQ’da esa biz ustuvor bo’lgan elementni (eng katta yoki eng kichkina elementni) o’chiramiz. PQ ikki amalni bajaradi: qo’shish (insert) va maksimumni (yoki minimumni) o’chirish (remove).
Priority queue uchun API yozish
Priority queue’ning ikki amali bo’lgani uchun, unga API yozib keyin boshqa funksiyalarda ishlatish qulay. Javascriptda Priority queue’ni ikki xil uslubda, tartiblangan array (ordered array) va tartiblanmagan array (unordered array) ko’rinishda ifodalashimiz mumkin.
Tartiblangan array. PQ’ga ma’lumot qo’shilganda u array’ning ohiriga qo’shiladi. So’ngra array Mergesort yordamida tartiblanadi. Ma’lumot o’chirishda PQ ning prioritetiga ko’ra, arrayning eng kichik elementi – birinchi elementi yoki arrayning eng katta elementi – ohirgi elementi arraydan o’chirilib, uning qiymati qaytariladi. Demak PQ’ni tartiblangan array ko’rinishida ifodalaganimizda ma’lumot qo’shish – O(N log N) – tartiblash hisobiga, ma’lumotni o’chirish O(1) bo’ladi.
Kod Githubda: https://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/priority-queues/priority-queues-ordered-array.js
Tartiblanmagan array. PQ’ga ma’lumot qo’shilganda u array’ning ohiriga qo’shiladi, ammo tartiblanmaydi. Ma’lumot o’chirishda PQ ning prioritetiga ko’ra, arrayning minimum yoki maksimum elementi indeksini topadi, so’ngra uni arrayning ohirgi elementi bilan solishtiradi. Agar minIndex yoki maxIndex arrayning ohirgi elementiga teng bo’lmasa, ularning o’rnini almashtiradi. Keying arrayning ohirgi elementini o’chirib, qiymatini qaytaradi.
PQ’ni tartiblangan array ko’rinishida ifodalaganimizda ma’lumot qo’shish – O(1), ma’lumotni o’chirish O(N) bo’ladi.
Kod Githubda: https://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/priority-queues/priority-queues-unordered-array.js
Ordered yoki unordered array versiyasidan foydalanish, PQ’ning nima maqsadda ishlatilishiga bog’liq. Agar PQ’ning insert funksiyasi ko’p ishlatilsa, unordered array foydaliroq; delete funksiyasi ko’p chaqirilsa, ordered array varianti tezroq ishlaydi.
Shuningdek, PQ’ni implementatsiyasi uchun binary heap ma’lumot tuzilmasidan foydalanish mumkin. Binary heap haqida keyingi maqolada gaplashamiz.
Ishlatishga misol
Faylda tranzaksiyalar ro’yhati mavjud. Ro’yhat uzunligi 1,000,000 yozuvdan ortiq.
Turing 6/17/1990 644.08 vonNeumann 3/26/2002 4121.85 Dijkstra 8/22/2007 2678.40 vonNeumann 1/11/1999 4409.74 Dijkstra 11/18/1995 837.42 Hoare 5/10/1993 3229.27 vonNeumann 2/12/1994 4732.35 Hoare 8/18/1992 4381.21 Turing 1/11/2002 66.10 Thompson 2/27/2000 4747.08 Turing 2/11/1991 2156.86 Hoare 8/12/2003 1025.70 vonNeumann 10/13/1993 2520.97 Dijkstra 9/10/2000 708.95 Turing 10/12/1993 3532.36 Hoare 2/10/2005 4050.20 ...
Biz ro’yhatning hammasini ekranga chiqara olmaymiz yoki array’ga yig’a olmaymiz, kontent juda katta bo’lib ketadi. Shuning uchun biz maksimum qiymatdagi 5ta tranzaksiyani tanlab olamiz. Maksimumni topish uchun narxlarni solishtiramiz.
Fayldan o’qish funksiyasining time complexity – O(M * N). M bu yerda 5 – max tranzaksiyalar soni.
* * *
Mavzu bo’yicha savollarni Github’dagi Webmaxor / leetcode-solutions repository’da yozishingiz yoki kodda Reference in new issue ni bosib, qoldirishingiz mumkin.