Laboratoriya ishi №1. Ma’lumotlarni saralash algoritmlarining murakkabligini tahlil qilish. Ustuvor navbatlar

Ustuvor navbatlar

Ustuvor navbatlar (ing. Priority queue) – oddiy navbatlarga o’xshash ammo bir qator xususiyatlarga ega abstract konteyner:

• 
  Ustuvor navbatning har bir elementiga shu elementning ustuvorligini belgilovchi qandaydir qiymat mos qo’yilgan. Prioritet bir biri bilan solishtirish orqali kiritiladi;
  
• 
  Ustuvor navbatdan element yechib olish funksiyasi qaysi elementning prioriteti maksimal bo’lsa o’shani qaytaradi.
  

Ko’plab ilovalarda yozuvlarni ularning kalitlarini o’sish tartibi bo’yicha qayta ishlashni talab qiladi, lekin bu qat’iy tartibda va hammasini birdaniga qilish degani emas. Ko’pchilik hollarda yozuvlar biron to’plamda yig’iladi va keyin maksimal kalitli yozuv qayta ishlanadi, shundan so’ng yana yozuvlarni yig’ish yana davom ettirilishi, so’ngra joriy kalitdan kattaroq kalitga ega yozuv qayta ishlanishi mumkin va h.k. Bunday ma’lumotlar strukturasi ustuvor navbat (priority queue) deb yuritiladi. Ustuvor navbatlardan foydalanish oddiy navbatlardan (eng eski element o’chiriladi) va steklardan (eng yangi element o’chiriladi) foydalanish kabi, ammo ulardan unumli foydalanish murakkabroq.