|
Heap tree ustida amal bajarish algoritmlari
|
| bet | 67/163 | | Sana | 16.01.2024 | | Hajmi | 18,84 Mb. | | #138868 |
Bog'liq O zbekiston respublikasi oliy va o rta maxsus ta lim vazirligi tHeap tree ustida amal bajarish algoritmlari
Heap tree ustida bajariladigan amallar:
Element qo’shish
Element o’chirish
Min-heapga yangi element kiritish algoritmi:
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 log2(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.
|
| |
