Toshkent Davlat Iqtisodiyot Universiteti To’rtkul fakulteti



Yüklə 98,1 Kb.
səhifə1/3
tarix28.11.2023
ölçüsü98,1 Kb.
#166797
  1   2   3
Презентация2

Toshkent Davlat Iqtisodiyot Universiteti To’rtkul fakulteti

211-ATT guruh talabasi Sa’dullayev Bobur Ma’lumotlar tuzilmasi va algoritm fani bo’yicha mustaqil ish.

REJA

Ustuvor navbatlarni piramida orqali qurish

  • Piramidaning muhim jihatlaridan biri bu, unda saqlanayotgan qiymatlarning maksimali uning tepasida joylashgan bo’ladi. Yuqorida keltirilgan faktlar bilan, ya’ni piramidani qayta tiklashning up() va down() amallari keltirilgandek piramidaning balandligidan oshmaydigan almashtirishlarni amalga oshiradi, bu esa ustuvor navbatlarni samarali qo’llashga imkon beradi.
  • Eng avvalo, bu qo’llash elementni tuzilmasini (chunki element faqat prioritetni emas balki qiymatni ham saqlaydi) tavsiflashni va piramida shakllantiriladigan massivni e’lon qilishni talab qiladi. Piramidani qayta tiklash amallari .priority maydonini solishtirishi lozim. Navbatning elementlari sonini saqlash uchun alohida size o’zgaruvchisi ajratiladi, konstruktorda unga 0 qiymati o’zlashtiriladi.

C++


static const int MAX_SIZE = 100;
struct Elem {
int val;
int priority;
Elem(int v = 0, int p = 0) {
val = v;
priority = p;
}
} a[MAX_SIZE];
int size;

Ustuvor navbatlarni piramida orqali qurish


Element qo’shish a[size] yacheykasida amalga oshiriladi. Chunki qo’shish amalga oshirilgandan so’ng piramidaning asosiy xususiyati buzilishi mumkin, shuning uchun qo’shimcha ravishta up() protsedurasini chaqirish talab etiladi. Qo’shish amalining umumiy murakkabligi O(logN) ga teng.
void enqueue(int value, int priority) {
if (size + 1 == MAX_SIZE)
/* navbatni to’ldirishdagi hatolikni qayta ishlash */
a[size++] = Elem(value, priority);
up(size - 1);
}

Yüklə 98,1 Kb.

Dostları ilə paylaş:
  1   2   3




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin