|
O'chirish
Ixtiyoriy elementni o'chirish quyidagi tarzda amalga oshirilishi mumkin:
Indeksni toping o'chirmoqchi bo'lgan element
Ushbu elementni oxirgi element bilan almashtiring
Qovoq xususiyatini tiklash uchun pastga-tepaga yoki yuqoriga ko'taring. Max-heap (min-heap) da, yuqoriga ko'tarish faqat elementning yangi kaliti bo'lganda kerak bo'ladi oldingi elementdan kattaroq (kichikroq), chunki faqat asosiy elementning heap-xususiyati buzilishi mumkin. Hep-xususiyati element o'rtasida haqiqiy bo'lgan deb taxmin qiling va uning elementlari elementni almashtirishdan oldin, uni endi kattaroq (kichikroq) kalit qiymati bilan buzib bo'lmaydi. Agar yangi kalit oldingisiga nisbatan kamroq (kattaroq) bo'lsa, unda faqat pastga tushirish kerak, chunki heap-xususiyati faqat asosiy elementlarda buzilishi mumkin.
Kalitni kamaytiring yoki oshiring
Reduktsiya tugmachasi operatsiyasi tugunning qiymatini berilgan qiymat bilan pastroq qiymatga almashtiradi, o'sish tugmachasi esa xuddi shunday qiladi, lekin yuqori qiymatga ega. Bunga berilgan qiymat bilan tugunni topish, qiymatni o'zgartirish va keyin yig'ish xususiyatini tiklash uchun pastga ko'tarish yoki ko'tarish kiradi.
Kichraytirish tugmachasini quyidagicha bajarish mumkin:
Biz o'zgartirmoqchi bo'lgan element indeksini toping
Tugun qiymatini kamaytiring
Uyma xususiyatini tiklash uchun pastga tushirish (maksimal yig'ishni nazarda tutgan holda)
Kattalashtirish tugmachasini quyidagicha bajarish mumkin:
Biz o'zgartirmoqchi bo'lgan element indeksini toping
Tugun qiymatini oshiring
Uyma xususiyatini tiklash uchun yuqoriga ko'taring (maksimal yig'indini nazarda tuting)
Uyum qurish
Qatoridan uyum qurish n kiritish elementlarini bo'sh uyumdan boshlash, so'ngra har bir elementni ketma-ket kiritish orqali amalga oshirish mumkin. Ikkilik uylar ixtirochisining nomidan Uilyamsning usuli deb nomlangan ushbu yondashuv osonlikcha ishga tushishi mumkin O(n jurnal n) vaqt: u bajaradi n qo'shimchalar O(log n) har birining narxi.[a]
Biroq, Uilyamsning usuli suboptimaldir. Tezroq usul (tufayli Floyd[8]) o'zboshimchalik bilan shakl xususiyatiga hurmat ko'rsatib, elementlarni ikkilik daraxtga qo'yishdan boshlanadi (daraxt massiv bilan ifodalanishi mumkin, pastga qarang). Keyin eng past darajadan boshlab yuqoriga qarab harakatlaning, har bir kichik daraxtning ildizini yo'q qilish algoritmida bo'lgani kabi pastga siljiting. Aniqrog'i, agar barcha baland daraxtlar balandlikdan boshlanadigan bo'lsa allaqachon "to'plangan" (eng past darajaga to'g'ri keladigan) ), balandlikdagi daraxtlar eng ko'p to'plangan uyni qurishda yoki eng kam qiymatli bolalarni qurishda ularning ildizlarini maksimal qiymatga ega bolalar yo'lidan pastga yuborish orqali kesilishi mumkin. Bu jarayon davom etadi tugun bo'yicha operatsiyalar (svoplar). Ushbu usulda vayronashning katta qismi quyi darajalarda sodir bo'ladi. Uyumning balandligi bo'lgani uchun , balandlikdagi tugunlar soni bu . Shuning uchun, barcha daraxtlarni yig'ish narxi:
Bunda berilgan cheksiz haqiqat ishlatiladi seriyali yaqinlashadi.
Yuqoridagilarning aniq qiymati (uyum qurish paytida taqqoslashning eng yomon holati) quyidagilarga teng
qayerda s2(n) bo'ladi ikkilik tasvirning barcha raqamlari yig'indisi ning n va e2(n) ning ko'rsatkichidir 2 ning asosiy faktorizatsiyasida n.
O'rtacha holatni tahlil qilish ancha murakkab, ammo uni asimptotik yaqinlashishini ko'rsatish mumkin 1.8814 n - 2 ta jurnal2n + O(1) taqqoslashlar.[10][11]
The Max-Heap qurish quyidagi funktsiya, massivni o'zgartiradi A to'liq binar daraxtni saqlaydigan n tugunlarni bir necha marta ishlatish orqali maksimal yig'ish Max-Heapify (max-heap uchun pastga-heapify) pastdan yuqoriga qarabzamin(n/2) + 1, zamin(n/2) + 2, ..., nbarchasi daraxt uchun barglardir (agar indekslar 1dan boshlanadi deb hisoblasak) - bu ularning har biri bitta elementli yig'indidir va pastga tushirish shart emas. Max-Heap qurish ishlaydiMax-Heapify qolgan daraxt tugunlarining har birida.
Do'stlaringiz bilan baham: | 
