Kampyuter injenering fakulteti 961-19 gurux 3-kurs talabasi Arslanov Sarvarning Ma’lumotlar tuzilmasi va algoritm fanidan

Kampyuter injenering fakulteti

961-19 gurux 3-kurs talabasi

Arslanov Sarvarning

Ma’lumotlar tuzilmasi va algoritm fanidan Mustaqil Ishi

Mavzu:Ikkilik uyum shaklida ma’lumotlar tuzilmalari.

Mundareja:

1.To'plam operatsiyalari

2.Kiritmoq

3. Qidirmoq

4. O'chirish

5.Kalitni kamaytiring yoki oshiring

6.Uyum qurish

7.To'pni amalga oshirish

8.Indeks tenglamalarini chiqarish

9.Bolalar tugunlari

10.Adabiyotlar

1.Toplam operatsiyalari.

To'liq ikkilamchi maksimal yig'ishning namunasi

To'liq binar min yig'indisining misoli

A ikkilik uyum a uyum ma'lumotlar tuzilishi a shaklini oladi ikkilik daraxt. Ikkilik uyumlar - bu amalga oshirishning keng tarqalgan usuli ustuvor navbat.^{[1]:162–163} Ikkilik uyma tomonidan kiritilgan J. W. J. Uilyams 1964 yilda ma'lumotlar tuzilishi sifatida kassa.^[2]

Ikkilik yig'ma ikkita qo'shimcha cheklovga ega bo'lgan ikkilik daraxt sifatida tavsiflanadi:^[3]

• 
  Shakli xususiyati: ikkilik uyma bu a to'liq ikkilik daraxt; ya'ni daraxtning barcha sathlari, ehtimol oxirgisidan tashqari (eng chuqur) to'liq to'ldirilgan va agar daraxtning oxirgi darajasi tugallanmagan bo'lsa, u darajadagi tugunlar chapdan o'ngga to'ldiriladi.
  
• 
  Heap xususiyati: har bir tugunda saqlanadigan tugun, ba'zi birlarga ko'ra, tugunning bolalaridagi tugmachalardan kattaroq yoki teng (≥) yoki undan kam yoki teng (≤). umumiy buyurtma.
  

Kiritish va olib tashlash operatsiyalari ham, avval to'pning oxiriga qo'shib yoki olib tashlash orqali, avval shakl xususiyatiga mos keladigan tarzda uyumni o'zgartiradi. Keyin uyum xususiyati uyadan yuqoriga yoki pastga qarab o'tish orqali tiklanadi. Ikkala operatsiya ham O (log) ni oladi n) vaqt.
Kiritmoq

Uyumga element qo'shish uchun biz ushbu algoritmni bajara olamiz:

1. 
   Elementni eng chap chap bo'shliqda to'pning pastki darajasiga qo'shing.
   
2. 
   Qo'shilgan elementni ota-onasi bilan solishtiring; agar ular to'g'ri tartibda bo'lsa, to'xtating.
   
3. 
   Agar yo'q bo'lsa, elementni ota-onasi bilan almashtiring va oldingi bosqichga qayting.
   

Tugunni ota-onasi bilan taqqoslash va almashtirish orqali yig'ish xususiyatini tiklaydigan 2 va 3-qadamlar deyiladi. tepalik operatsiya (shuningdek ma'lum qabariq, shokoladli, saralash, dam olish, suzish, qirib tashlash, yoki kaskadli).

Amalga oshiriladigan operatsiyalar soni faqat yig'ilish xususiyatini qondirish uchun yangi element ko'tarilishi kerak bo'lgan darajalar soniga bog'liq. Shunday qilib, kiritish operatsiyasi O ning eng yomon vaqt murakkabligiga ega (log n). Tasodifiy uyum uchun va takroriy qo'shimchalar uchun kiritish operatsiyasi O (1) ning o'rtacha holatdagi murakkabligiga ega.^[4][5]

Ikkilik uyumni kiritish misoli, bizda maksimal yig'im bor deb ayting

va biz yig'indiga 15 raqamini qo'shmoqchimiz. Biz birinchi navbatda 15-ni X tomonidan belgilangan joyga joylashtiramiz. Biroq, yig'ma mulk buzilgan 15 > 8, shuning uchun biz 15 va 8 ni almashtirishimiz kerak, shuning uchun birinchi almashtirishdan keyin bizda uyum quyidagicha ko'rinadi:

Biroq, hanuzgacha mulk buzilgan 15 > 11, shuning uchun yana almashtirishimiz kerak:

bu haqiqiy max. Ushbu oxirgi bosqichdan keyin chap bolani tekshirishga hojat yo'q: boshida maksimal yig'ish to'g'ri edi, ya'ni ildiz allaqachon chap bolasidan kattaroq edi, shuning uchun ildizni yanada katta qiymatga almashtirish bu xususiyatni saqlab qoladi har bir tugun o'z farzandlaridan kattaroq (11 > 5; agar 15 > 11va 11 > 5, keyin 15 > 5, chunki o'tish munosabati).

Ekstrakt

Qovuq xususiyatini saqlab qolgan holda, ildizni uyumdan o'chirish tartibi (max-heapdagi maksimal elementni yoki min-heapdagi minimal elementni samarali ravishda ajratib olish).

1. 
   To'pni ildizini oxirgi darajadagi oxirgi element bilan almashtiring.
   
2. 
   Yangi ildizni farzandlari bilan solishtiring; agar ular to'g'ri tartibda bo'lsa, to'xtating.
   
3. 
   Agar yo'q bo'lsa, elementni bolalaridan biri bilan almashtiring va oldingi bosqichga qayting. (Kichikroq bolasi bilan min-uyumda, kattaroq bolasi esa maksimalda).
   

Tugunni o'z farzandlaridan biri bilan taqqoslash va almashtirish orqali to'plash xususiyatini tiklaydigan 2 va 3-qadamlar deyiladi uyum (shuningdek, nomi bilan tanilgan qabariq pastga, perkolad pastga, saralash, cho'kish, pastga tushmoq, heapify pastga, kaskad pastga, ekstrakt-min yoki ekstrakt-maxyoki oddiygina qirib tashlamoq) operatsiya.

Shunday qilib, agar bizda avvalgidek max-heap bo'lsa

Biz 11ni olib tashlaymiz va uni 4 ga almashtiramiz.

Endi yig'ish xususiyati buzilgan, chunki 8 dan katta bo'lganligi sababli, bu holda ikkita elementni almashtirish 4 va 8, yig'ish xususiyatini tiklash uchun etarli bo'ladi va biz elementlarni boshqa almashtirishimiz shart emas:

Pastga qarab harakatlanadigan tugun bilan almashtiriladi kattaroq Maksimal uyumdagi bolalaridan (kichik uyumda u kichikroq bolasi bilan almashtirilishi mumkin), u yangi vaziyatda yig'ilish xususiyatini qondirmaguncha. Ushbu funktsiyaga Max-Heapify funktsiyasini quyida keltirilgan psevdokod uchun qator- orqa o'rindiq A uzunlik uzunlik(A). Yozib oling A 1dan boshlab indekslanadi.

// Max-heap uchun pastga yoki heapify-pastga operatsiyasini bajaring // A: 1 // dan boshlab indekslangan, uyumni ifodalovchi qator. men: pastga tushganda boshlanadigan indeksMax-Heapify(A, men): chap ← 2×men to'g'ri ← 2×men + 1 eng katta ← men agar chap ≤ uzunlik(A) va A[chap]> A [eng katta] keyin: eng katta ← chap