|
top() – Prioritet navbatidagi maksimal ustuvor elementni qaytarish.
Amalga oshirish
|
| bet | 2/7 | | Sana | 13.06.2024 | | Hajmi | 208,96 Kb. | | #263487 | | Turi | Referat |
Bog'liq 1. Stack. queue.priority queue.Bu sahifa navigatsiya:
- class
top() – Prioritet navbatidagi maksimal ustuvor elementni qaytarish.
Amalga oshirish
Biz ustuvor navbatlarni amalga oshirishning turli usullarini o’ylashimiz mumkin. Ustuvor navbatlarning ishlashini samarali qilish uchun biz massiv, bog’langan ro’yxat, BST, to’plamlar kabi turli xil ma’lumotlar tuzilmalarini tanlashimiz mumkin.
Ustuvor navbat elementining tuzilishi bo’ladi
class Node {
int data
int priority
}
Massiv orqali amalga oshirish
Biz ustuvor navbatning elementlarini saqlaydigan massivni olamiz. Shunday qilib, navbat operatsiyasi doimiy vaqt operatsiyasi bo’lgan massiv oxirida amalga oshiriladi.
Biroq, navbatni bekor qilish uchun biz massivdagi eng yuqori ustuvor elementni topishimiz va uni massivdan o’chirishimiz kerak. Massivdagi o’chirish va qidirish jarayoni chiziqli vaqtni oladi. Xuddi shunday, top() ham eng yuqori ustuvor elementni qidirish uchun chiziqli vaqtni oladi.
Shunday qilib, massiv bilan
enqueue() doimiy vaqtni oladi.
dequeue() chiziqli vaqtni oladi.
top() chiziqli vaqtni oladi.
Endi, agar biz massivning ustuvorlikka nisbatan tartibini saqlasak, enqueue() chiziqli vaqtni oladi va dequeue() va top() doimiy vaqtni oladi.
Bog'langan ro'yxat orqali amalga oshirish
Bog'langan ro'yxat shunday yaratilishi mumkinki, eng yuqori ustuvor element old tomonda bo'lishi kerak. Bog'langan ro'yxat kamayib boruvchi ustuvorlik tartibida joylashtirilishi mumkin. Shunday qilib, dequeue() operatsiyasi doimiy vaqt talab qilishi mumkin.
Enqueue() ishlashi uchun biz bog'langan ro'yxatni aylanib o'tishimiz va tugunni kiritish uchun to'g'ri joyni topishimiz kerak, shunda ustuvor navbatning umumiy tartibi saqlanib qoladi. Bu chiziqli vaqtni oladi, ammo qolgan ikkita operatsiya, ya'ni dequeue() va top() doimiy vaqtda bajarilishi mumkin.
|
| |
