Massiv orqali tasvirlangan piramida Piramidaning asosiy xususiyati Piramidani qayta tiklash – up amali

Laboratoriya mashg’uloti №5. Murakkab ma’lumotlar tuzilmalari: Piramida.

Reja:

1. 
   Massiv orqali tasvirlangan piramida
   
2. 
   Piramidaning asosiy xususiyati
   
3. 
   Piramidani qayta tiklash – up() amali
   
4. 
   Piramidani qayta tiklash – down() amali
   

Nazariy qism

Piramida - bu ikkilik daraxt bo'lib, uning elementlari uchun qo'shimcha shart (piramidaning asosiy xususiyati deb ataladi) bajariladi: ajdod tugunidagi elementning qiymati barcha avlod tugunlaridagi qiymatlardan kattaroq (aniqrog'i, kam emas).

Massiv orqali tasvirlangan piramida

Elementlarning o'zaro bog'liqligini aniqlash uchun massivning katakchalari indekslari orasidagi o'zaro bog'liqlikdan foydalanib, piramidani massiv orqali qurish mumkin. Rasmda 8 elementdan iborat piramida va uning massivi xaritasi keltirilgan.

Massiv elementlarini indekslash birdan boshlansa, u holda i indeksli elementning to’g’ridan-to’g’ri avlodlari indeksi (2*i) va (2*i+1) tarzida bo’ladi, uning ajdodi esa (i/2) indeksli element bo’ladi. Shundan kelib chiqqan holda, 1 indeksli elementning avlodlari 2 va 3 indeksli elementlar bo’ladi, 2 indeksli elementning avlodlari – 4 va 5 indeksli elementlar, 8 indeksli elementning ajdodi 4 indeksli element bo’ladi.

Agar elementlarning indeksatsiyasi 0 dan boshlansa, u holda i indeksli elementning avlodlari (2*i+1) va (2*i+2) indeksli elementlar bo’ladi va biror elementning ajdodining indeksi ((i-1)/2) ga teng element hisoblanadi. Bundan kelib chiqadiki, 0 indeksli elmentning avlodlari 1 va 2 indeksli elementlar, 1 indeksli elementning avlodlari – 3 va 4 indeksli elementlar hisoblanadi, 7 indeksli elementning ajdodi 3 indeksli element bo’ladi.

Ketingi kodni osonlashtirish maqsadida yordamchi parent(). leftChild() va rightChild() funksiyalarini belgilab olamiz:

int parent(int i) {

return (i - 1) / 2;

}
int leftChild(int i) {

return 2 * i + 1;

}
int rightChild(int i) {

return 2 * i + 2;

}

Berilgan ko’rinishda piramida tashkil qilinsa, to’liq ikkilik daraxt hisoblanadi: faqat eng quyi daraja to’ldirilmasligi mumkin va uning to'ldiri’ishi qat’iy chapdan o’ngga amalga oshiriladi. Ko’rsatish mumkinki, N ta elementli piramidada [N/2] oxirgi element barg hisoblanadi, ya’ni avlodga ega bo’lmaydi. Birdan boshlab indekslanganda massivdagi barglar (N/2+1) dan N gacha indeksga, noldan boshlab indekslanganda esa – (N/2) dan (N-1) gacha indeksga ega bo’ladi.

Piramidaning balandligi - bu piramidaning yuqori qismidan har qanday bargga qadar bo'lgan eng uzun yo'ldagi qirralarning soniga aytiladi. Bundan kelib chiqadiki, N ta elementli piramidaning butun balandligi ⌊log₂N⌋ ga teng.
Piramidaning asosiy xususiyatini qo’llab – quvvatlash

Piramidaga qandaydir element qo’shish, o’zgartirish yoki o’chirish piramidaning asosiy xususiyatini o’zgartirishi mumkin. Har qanday shunga o’xshash buzilishlarni asosiy ikki turga ajratish mumkin:

• 
  Elementning qiymati ajdodinikidan katta va shu sababdan u joriy o’rniga nisbatan yuqori o’rinni egallashi lozim;
  
• 
  Elementning qiymati xech bo’lmaganda bitta avlodinikidan kichik va shu sababdan u joriy o’rniga nisbatan pastdagi o’rinni egallashi lozim.
  

Piramidani qayta tiklash – up() amali

up() protsedurasi birinchi turdagi buzilishni to’g’irlashni amalga oshiradi, u berilgan elementni uning ajdodi bilan toki elementning qiymati ajdodinikidan kichik bo’lmaguniga qadar yoki qiymat piramidaning yuqorisiga joylashmaguniga qadar almashtiradi. Protsedura piramidaning asosiy xususiyatini buzuvchi element indeksini qabul qiladi. Quyida keltirilgan kod indekslash noldan boshlangan massiv uchun o’rinli.

void up(int i) {

while (i != 0 && a[i] > a[parent(i)]) {

swap(a[i], a[parent(i)];

i = parent(i);

}

}


Piramidani qayta tiklash – down() amali

down() protsedurasi ikkinchi turdagi buzilishlarni to’g’irlashga qaratilgan, u berilgan elementni o’zidan kata avlodlari bilan toki element qiymati avlodlari qiymatidan katta bo’lmaguniga qadar yoki element bargga aylanguniga qadar almashtiradi. Almashinuv maksimal avlodlar bilan amalga oshiriladi, chunki faqatgina bu holatda piramidaning asosiy xususiyati almashinuvdan keyin ham ta'minlanishi kafolatlanadi. Oldingi holatdagi kabi protsedura massivda noto’g’ri joylashgan elelment indeksini oladi, indekslash esa noldan boshlanadi. Navbatning umumiy elementlari soni size ga teng.

void down(int i) {

while (i < size / 2) {

int maxI = leftChild(i);

if (rightChild(i) < size && a[rightChild(i)] > a[leftChild(i)])

maxI = rightChild(i);

if (a[i] >= a[maxI])

return;

swap(a[i], a[maxI]);

i = maxI;

}

}

Nazorat savollari:

1. 
   Piramidani nimalar orqali tasvirlash mumkin?
   
2. 
   Uning tuzilishini tushuntirib bering?
   
3. 
   Piramida elementlari ustida bajariladigan amallarni ayting?