Al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti

Priority Queue – Bu oddiy queue ga o’xshash lekin unda ozroq farq qiladi.

Oddiy Queue da First-In-First-Served prinsipi amal qilsa Ustuvor navbatlarda esa har bir massiv elementida ustuvorlikni ofidalovchi yana bir qiymat mavjud bo’ladi. Va aynan shu element queue ni elementlarini ifodalab beradi.

Priority Queue ni asosiy amallari:

• 
  insert / enqueue - navbatning orqa tomoniga element qo'shing.
  
• 
  Remove / dequeue - navbatning old qismidan biror narsani olib tashlang.
  

Bu strukturada massivga element qo’shish va ularni o’chirish quyidagi ko’rinishda amalga oshiriladi:

Informatika fanida har bir element qo'shimcha ravishda "ustuvorlik" ga ega bo'lgan oddiy navbat yoki stek ma'lumotlar tuzilishiga o'xshash mavhum ma'lumotlar turi. Prioritetli navbatda, ustuvorligi yuqori bo'lgan element ustunligi past bo'lgan elementdan oldin xizmat qiladi. Ba'zi dasturlarda, agar ikkita element bir xil ustuvorlikka ega bo'lsa, ular ularga berilgan tartibda xizmat ko'rsatiladi, boshqa dasturlarda esa bir xil ustuvorlikka ega elementlarning buyurtmasi aniqlanmagan.

Imtiyozli navbatlar ko'pincha uyum bilan amalga oshirilsa-da, ular kontseptual jihatdan uyumlardan ajralib turadi. Prioritet navbat - bu "ro'yxat" yoki "xarita" kabi tushuncha; ro'yxatni bog'langan ro'yxat yoki qator bilan amalga oshirish mumkin bo'lganidek, ustuvor navbatni uyum yoki tartibsiz qator kabi turli xil usullar bilan amalga oshirish mumkin.

Ustuvor navbatlar asosida ishlovchi massivda element qo’shish java dasturlash tilida quyidagicha ifodalanadi:

void insert(int data){

int i = 0;

if(!isFull()){

// agar navbat bo’sh yoki to’lmagan bo’lsa

if(itemCount == 0){

intArray[itemCount++] = data;

}else{

//

for(i = itemCount - 1; i >= 0; i-- ){

//

if(data > intArray[i]){

intArray[i+1] = intArray[i];

}else{

break;

}

}

//

intArray[i+1] = data;

itemCount++;

}

}

}
int removeData(){

return intArray[--itemCount];

}
int main() {

/* */

insert(3);

insert(5);

insert(9);

insert(1);

insert(12);
// ------------------

// index : 0 1 2 3 4

// ------------------

// queue : 12 9 5 3 1

insert(15);
// ---------------------

// index : 0 1 2 3 4 5

// ---------------------

// queue : 15 12 9 5 3 1

if(isFull()){

printf("Queue to’lgan!\n");

}
//

int num = removeData();

printf("Element o’chirildi: %d\n",num);

// ---------------------

// index : 0 1 2 3 4

// ---------------------

// queue : 15 12 9 5 3
//

insert(16);

// ----------------------

// index : 0 1 2 3 4 5

// ----------------------

// queue : 16 15 12 9 5 3

//

insert(17);

insert(18);
// ----------------------

// index : 0 1 2 3 4 5

// ----------------------

// queue : 16 15 12 9 5 3

printf("Eng boshidagi element %d\n - ",peek());
printf("----------------------\n");

printf("index : 5 4 3 2 1 0\n");

printf("----------------------\n");

printf("Queue: ");

while(!isEmpty()){

int n = removeData();

printf("%d ",n);

}

}
Natija:

Queue to’lgan!

Element o’chirildi: 1

Eng boshidagi element: 3

----------------------

index : 5 4 3 2 1 0

----------------------

Queue: 3 5 9 12 15 16

Xulosa:

Ustuvor navbat - bu har bir element ustuvorlik bilan bog'liq bo'lgan va uning ustuvorligiga muvofiq xizmat ko'rsatadigan navbatning maxsus turi. Agar bir xil ustuvorlikka ega elementlar yuzaga kelsa, ular navbatdagi navbatga muvofiq xizmat ko'rsatiladi.

Odatda ustunlikni belgilash uchun elementning o'zi hisobga olinadi.

Masalan, eng yuqori qiymatga ega element eng yuqori ustuvor element sifatida qabul qilinadi. Ammo, boshqa holatlarda, biz eng past ustuvor element sifatida eng past qiymatga ega elementni qabul qilishimiz mumkin. Boshqa hollarda, biz ehtiyojlarimizga qarab ustuvor vazifalarni belgilashimiz mumkin.

Foydalanilgan adabiyotlar va saytlar:

1. Томас Х.Кормен «Алгоритмы. Вводный курс» 2014 г.

2.fayllar.org, https://en.wikipedia.org, Ziyonet axborot talim portal

3. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "Section 6.5: Priority queues". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 138–142.