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

Max-Heap qurish (A): har biriga indeks men dan zamin(uzunlik(A)/2) pastga 1 bajaring: Max-Heapify(A, men)

To'pni amalga oshirish

Massivda saqlangan kichik to'liq binar daraxt

Ikkilik yig'ma va qatorni amalga oshirish o'rtasidagi taqqoslash.

To'plar odatda an bilan amalga oshiriladi qator. Har qanday ikkilik daraxtni massivda saqlash mumkin, lekin ikkitomonlama har doim to'liq ikkilik daraxt bo'lgani uchun uni ixcham holda saqlash mumkin. Buning uchun joy kerak emas ko'rsatgichlar; Buning o'rniga, har bir tugunning ota-onasi va farzandlarini arifmetik yordamida massiv indekslari bo'yicha topish mumkin. Ushbu xususiyatlar bu uyumni amalga oshirishni an ning oddiy misoliga aylantiradi yashirin ma'lumotlar tuzilishi yoki Ahnentafel ro'yxat. Tafsilotlar ildiz holatiga bog'liq, bu esa o'z navbatida a ning cheklovlariga bog'liq bo'lishi mumkin dasturlash tili amalga oshirish uchun yoki dasturchining afzalligi uchun ishlatiladi. Aniqrog'i, ba'zida arifmetikani soddalashtirish uchun ildiz 1 indeksiga joylashtiriladi.

Ruxsat bering n uyumdagi elementlar soni va men uyumni saqlaydigan qatorning o'zboshimchalik bilan yaroqli indekslari bo'lishi. Agar daraxt ildizi 0 indeksida bo'lsa, indekslari 0 dan 0 gacha n - 1, keyin har bir element a indeksda men bor

• 
  bolalar indekslari bo'yicha 2men + 1 va 2men + 2
  
• 
  uning ota-onasi indeks bo'yicha zamin((men − 1) ∕ 2).
  

Shu bilan bir qatorda, agar daraxt ildizi 1 indeksida bo'lsa, unda 1 dan 1 gacha bo'lgan indekslar mavjud n, keyin har bir element a indeksda men bor

• 
  bolalar indekslari bo'yicha 2men va 2men +1
  
• 
  uning ota-onasi indeks bo'yicha zamin(i ∕ 2).
  

Ushbu dastur kassa algoritm, bu erda massivni saqlash uchun kirish massividagi bo'shliqni qayta ishlatishga imkon beradi (ya'ni algoritm bajariladi) joyida). Amalga oshirish a sifatida foydalanish uchun ham foydalidir Birinchi navbat qaerda foydalanish a dinamik qator cheksiz ko'p narsalarni kiritish imkonini beradi.

Keyin yuqoriga ko'tarish / tushirish operatsiyalari massivda quyidagicha ifodalanishi mumkin: indekslar uchun b, b+1, ..., e. Sif-down funktsiyasi heap xususiyatini kengaytiradi b−1, b, b+1, ..., e.Faqat indeks men = b$ Frac {1} $ birikma xususiyatini buzishi mumkin j ning eng katta farzandining ko'rsatkichi bo'lishi a[men] (maksimal uyum uchun yoki eng kichik bola uchun min-uyum uchun) oralig'ida b, ..., e. (Agar bunday indeks mavjud bo'lmasa, chunki 2men > e keyin heap xususiyati yangi kengaytirilgan diapazonga ega bo'ladi va hech narsa qilish kerak emas.) Qadriyatlarni almashtirish orqali a[men] va a[j] lavozim uchun yig'ilish xususiyati men Ushbu nuqtada, bitta muammo shundaki, heap xususiyati indeksga mos kelmasligi mumkin j.Silt-down funktsiyasi qo'llaniladi quyruq-rekursiv indekslash j barcha elementlar uchun yig'ilish xususiyati o'rnatilgunga qadar.

Saralash funktsiyasi tez. Har bir qadamda unga faqat ikkita taqqoslash va bitta almashtirish kerak. U ishlayotgan indeks qiymati har bir iteratsiyada ikki baravar ko'payadi, shunda ko'pi bilan log bo'ladi₂ e qadamlar talab qilinadi.

Katta uyumlar va ishlatish uchun virtual xotira, yuqoridagi sxema bo'yicha elementlarni massivda saqlash samarasiz: (deyarli) har bir daraja boshqacha sahifa. B-uyumlar subtreesni bitta sahifada saqlaydigan, kiradigan sahifalar sonini o'n baravarga kamaytiradigan ikkilik yig'indilar.^[12]

Ikki binar uyumni birlashtirish amali Θ (n) teng o'lchamdagi uyumlar uchun. Siz qila oladigan eng yaxshi narsa (agar massivni amalga oshirishda bo'lsa) shunchaki ikkita yig'ma qatorni birlashtirish va natijada to'plashdir.^[13] Bir uyum n elementlarni uyum bilan birlashtirish mumkin k O dan foydalanadigan elementlar (log n jurnal k) asosiy taqqoslashlar yoki ko'rsatgichga asoslangan holda, O (log.) n jurnal k) vaqt.^[14] Uyumni ajratish algoritmi n elementlarni ikkita uyumga aylantiradi k va n-k elementlar, navbati bilan, uyumlarning yangi ko'rinishiga asoslanib, subheaplarning tartiblangan to'plamlari sifatida taqdim etilgan.^[15] Algoritm uchun O (log) kerak n * log n) taqqoslashlar. Ko'rinishda, shuningdek, uyumlarni birlashtirish uchun yangi va kontseptual jihatdan sodda algoritm mavjud. Birlashish odatiy vazifa bo'lsa, masalan, boshqa biron bir yig'ma dastur tavsiya etiladi binomiy uyumlar, bu O (log) da birlashtirilishi mumkin n).

Bunga qo'shimcha ravishda, ikkilik birikma an'anaviy ma'lumotlar bazasi binosi bilan amalga oshirilishi mumkin, ammo elementni qo'shganda qo'shni elementni ikkilik uyumda topishda muammo yuzaga keladi. Ushbu elementni algoritmik ravishda yoki tugunlarga qo'shimcha ma'lumotlarni qo'shish orqali aniqlash mumkin, bu daraxtni "torlash" deb nomlanadi - shunchaki bolalarga havolalarni saqlash o'rniga, biz tartibda; ... uchun tugunning vorisi ham.

Eng kichik va eng katta elementlarni ajratib olish uchun uyum tuzilishini o'zgartirish mumkin   vaqt.^[16] Buning uchun qatorlar min heap va max-heap o'rtasida o'zgarib turadi. Algoritmlar taxminan bir xil, ammo har bir qadamda o'zgaruvchan taqqoslash bilan o'zgaruvchan qatorlarni ko'rib chiqish kerak. Ishlash odatdagi bitta yo'nalish uyumiga o'xshaydi. Ushbu g'oyani min-max-median uyumiga umumlashtirish mumkin.

Indeks tenglamalarini chiqarish

Massivga asoslangan uyumda tugunning bolalari va ota-onalari tugun indeksidagi oddiy arifmetik orqali joylashishi mumkin. Ushbu bo'limda 0-indeksda ildizi bo'lgan uyumlar uchun tegishli tenglamalar keltirilgan va ularning indekslari 1-da bo'lgan ildizlari bilan qo'shimcha yozuvlar mavjud.

Chalkashmaslik uchun biz quyidagini aniqlaymiz Daraja tugunning ildizi uning ildizdan uzoqligi, chunki ildizning o'zi 0 darajani egallaydi.

Bolalar tugunlari

Indeksda joylashgan umumiy tugun uchun   (0 dan boshlab), avval uning o'ng farzandining indeksini olamiz,  .

Tugun qilaylik   darajasida joylashgan bo'lishi  , va har qanday darajaga e'tibor bering   to'liq o'z ichiga oladi   tugunlar. Bundan tashqari, aniq narsalar mavjud   qatlamgacha bo'lgan qatlamlarni o'z ichiga olgan tugunlar   (ikkilik arifmetikani o'ylab ko'ring; 0111 ... 111 = 1000 ... 000 - 1). Ildiz 0 da saqlanganligi sababli  th tugun indeksda saqlanadi  . Ushbu kuzatuvlarni birlashtirib, uchun quyidagi ifoda hosil bo'ladi l qatlamidagi oxirgi tugunning ko'rsatkichi.

Bo'lsin   tugundan keyingi tugunlar   L qatlamida shunday

Ularning har biri   tugunlarda to'liq 2 ta bola bo'lishi kerak, shuning uchun ham bo'lishi kerak   tugunlarni ajratish  qatlamining oxiridan o'ng bolasi ( ).

Talab qilinganidek.

Har qanday tugunning chap bolasi har doim o'ng farzandidan 1 o'rin oldinda ekanligini ta'kidlab, biz olamiz  .

Agar ildiz 0 o'rniga 1 indeksida joylashgan bo'lsa, har bir darajadagi so'nggi tugun o'rniga indeksda bo'ladi  . Buni hosil davomida ishlatish   va   ularning ildizi 1 ga teng bo'lgan uyumlar uchun.

Ota-ona tuguni

Har bir tugun ota-onasining chap yoki o'ng farzandidir, shuning uchun biz quyidagilarning ikkalasi ham to'g'ri ekanligini bilamiz

Endi bu iborani ko'rib chiqing .

Agar tugun bo'lsa   chap bola, bu darhol natijani beradi, ammo tugun bo'lsa ham to'g'ri natijani beradi   to'g'ri bola. Ushbu holatda,   teng bo'lishi kerak va shu sababli   g'alati bo'lishi kerak

Shuning uchun, tugunning chap yoki o'ng bolasi bo'lishidan qat'i nazar, uning ota-onasini quyidagi ibora bilan topish mumkin