O’zbekiston respublikasi oliy va o’rta maxsus ta’lim vazirligi toshkent axborot texnologiyalari universiteti

Heap tree ustida amal bajarish algoritmlari
Heap tree ustida bajariladigan amallar:

• 
  Element qo’shish
  
• 
  Element o’chirish
  

Min-heapga yangi element kiritish algoritmi:

• 
  Yangi elementni massivning navbatdagi indeksiga joylash;
  
• 
  Yangi elementni ota tugun bilan solishtiring, agar yangi element otasidan kichik bo’lsa, ularni o’rin almashtiring;
  
• 
  Bu jarayon takrorlanadi toki:
  
  • 
    Yoki yangi elementning otasi kichik yoki teng bo’lguncha;
    
  • 
    Yoki yangi element ildizga kelguncha (massivda 0 indeksga kelguncha).
    

Min-heapga yangi 43 sonini kiritamiz. Min-heapga 18 ni kiritamiz.

Min-heapga 2 ni kiritamiz.

Min-heap treedan elementni o’chirish algoritmi:

• 
  O ’chiriladigan element o’rniga daraxtdagi eng quyi darajada turgan eng o’ngdagi, ya’ni oxirgi element joylashtiriladi.
  
• 
  O’rni o’zgargan shu element ikkita o’g’il tugunlari bilan solishtiriladi va agar ulardan katta bo’sa, kichik o’g’il tugunl bilan almashtiriladi.
  
• 
  O’rinlashtirishda qatnashgan element ta’sir qiladigan qism daraxtlar tekshirib chiqiladi, buning uchun oxirgi ikkita amal takrorlanadi.
  

Masalan, 13.3-rasmdagi heap treedan 5 ni o’chiramiz. Quyidagi heap tree xosil bo’ladi.

Agar bundan 14 ni o’chirsak, quyidagi ko’rinishga keladi:

Heap tree tuzilmasi bilan ishlash samaradorligi:
Agar tuzilmada N ta element mavjud bo’lsa, undagi bosqichlar soni log₂(N+1) ta teng.

• 
  Yangi element kiritishda 1ta boqsichda 1ta elementdan k’op bo’lmagan o’rinlashtirish bajarilishi sababli kiritish samaradorligi O(lon(n)) gat eng.
  
• 
  Element o’chirishda ham xar bir bosqichda faqat 1 ta o’rinlashtirish bajarilishi mumkinligi sababli o’chirish samaradorligi O(log(n)) gat eng.