O’zbekiston Respublikasi Axborot Texnologiyalari va Komunikatsiyalarini rivojlantirish Vazirligi Muhammad al-Xorazmiy nomidagi Toshkent Axborot Texnologiyalari Universiteti

O’zbekiston Respublikasi Axborot Texnologiyalari va Komunikatsiyalarini rivojlantirish Vazirligi Muhammad al-Xorazmiy nomidagi Toshkent Axborot Texnologiyalari Universiteti

5-Laboratoriya ishi

Bajardi: CAL007-L3-guruh talabasi

Sobirov Akhmadjon

Toshkent 2020
Piramida elementlarini saralash:

#include iostream

using namespace std;

an index in arr[]. n is size of heap

void heapify(int arr[], int n, int i)

{

int largest = i;

int l = 2i + 1; left = 2i + 1

int r = 2i + 2; right = 2i + 2

if (l n && arr[l] arr[largest])

largest = l;

if (r n && arr[r] arr[largest])

largest = r;

if (largest != i)

{

swap(arr[i], arr[largest]);

heapify(arr, n, largest);

}

}

void heapSort(int arr[], int n)

{

for (int i = n 2 - 1; i = 0; i--)

heapify(arr, n, i);

for (int i=n-1; i0; i--)

{

swap(arr[0], arr[i]);

call max heapify on the reduced heap

heapify(arr, i, 0);

}

}

void printArray(int arr[], int n)

{

for (int i=0; in; ++i)

cout arr[i] ;

cout n;

}

int main()

{

int arr[] = {4, 10, 3, 5, 1};

int n = sizeof(arr)sizeof(arr[0]);

heapSort(arr, n);

cout<<” Saralangan massiv\n” ;

printArray(arr, n);

}

Kiritilganma`lumot: 4, 10, 3, 5, 1

4(0)

/ \

10(1) 3(2)

/ \

5(3) 1(4)

Qavs ichidagi sonlar indeksni bildiradi ma`lumotni e`lon qilishdagi:

Piramidada eng katta elementga murojat qilamiz ya`ni index 1 ga:

4(0)

/ \

10(1) 3(2)

/ \

5(3) 1(4)

Va eng katta elementni piramida uchiga index 0 ga joylashdirdik:

10(0)

/ \

5(1) 3(2)

/ \

4(3) 1(4)

Nazorat savollari:

1. 
   Piramidani nimalar orqali tasvirlash mumkin?
   
2. 
   Uning tuzilishini tushuntirib bering?
   

3.Piramida elementlari ustida bajariladigan amallarni ayting?

Javoblar:

1.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;

}

• 
  2.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.
  

3.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;

}

}

Xulosa:

Men bu labaratorya ishida murakkab tuzulma (Piramida) asosida kod yozdim va uni o`rgandim.