Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti tizimli va amaliy dasturlashtirish kafedrasi

heap operatsiyalari 
Uyum operatsiyalarining ishlash vaqtlarini tushunish uchun, 
qo'shish va o'chirishning heap ichida qanday ishlashini tushunish 
juda muhimdir
. 
Kiritish 
heapga yangi element kiritilganda, u heap
ning toʻliq shaklini 
saqlab qolish uchun toʻplamning keyingi boʻsh joyiga, eng oxirgi 
sathining eng oʻng joyiga qoʻshiladi. Biroq, bu yangi element 
to'pning boshqa asosiy xususiyatini, uning tartibini buzishi 
mumkin. 
Bir daqiqada, agar yangi elementning bos elementi undan katta 
bo'lsa, u bosh element bilan almashtiriladi. 
Bu element toʻpning 
ildiziga yetguncha yoki toʻgʻri tartibda joylashtirilgunga qadar 
daraxtda 
koʻtarilib
turadi . Xuddi shu jarayon maksimal to'plar 
uchun ham amal qiladi, lekin tugunning to'g'ri holatda ekanligini 
tekshirish uchun asosiy tugun yangi tugundan kattaroq bo'lishi 
kerak. 

Olib tashlash 
heapdan olib tashlashda ildiz tugun har doim olib tashlanadi. Keyin, oxirgi 
element, yig'ishning oxirgi darajasidagi eng o'ng tugun, olib tashlanadi va 
ildiz sifatida o'rnatiladi. Bu olib tashlash jarayoni to'p shaklini saqlab qoladi, 
lekin bu yangi tartib heapning to'g'ri tartibini buzishi mumkin. 
Bir daqiqada, agar yangi elementning bolalaridan biri ularning ota-onasidan 
kichik bo'lsa, yangi element ikkita boladan kichigi bilan almashtiriladi. Bu 
element 
toʻpning oxirgi darajasiga yetguncha yoki toʻgʻri joyga oʻrnatilgunga 
qadar daraxtda 

Download 0,72 Mb.