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
