Ma’lumotlar tuzilmasi va algoritmlar

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

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

Heap treeni tashkil etish usullari va samaradorligi

Heap treeni dasturda massiv ko’rinishida ifodalash mumkin, ya’ni barcha heap tuzilmalarni massiv ko’rinishida ifodalash mumkin, lekin barcha massivlar heap bo’lmaydi. Berilgan massiv elementlarini shunday joylash kerakki, natija heap treeni ifodalasin. Buning bir necha usullari mavjud. Eng soddasi bo’sh heapga ketma-ket elementlarni joylash bilan amalga oshiriladi. Bu “tepadan-pastga” usuli (ya’ni elementlar heapga yuqorida keltirilgan yangi element qo’shish algoritmi bilan kiritiladi) bo’lib, Jogn Williams tomonidan taklif etilgan. Quyida rasmda “tepadan-pastga” algoritmi ifodalangan va dasturi keltirilgan.

13.6-rasm. Heap treeni “tepadan-pastga” usuli bilan tashkil etish.

Bu algoritm samaradorligini eng yomon holatda tekshiradigan bo’lsak, unga kiritilgan xar bir element ildizgacha yuqoriga xarakat qilishi kerak. Bunda k ta elementdan iborat bo’lgan heapda yangi kiritilgan element yuqoriga xarakat qilishi uchun [lg k] ta o’rin almashtirishlar amalga oshirilishi kerak. Agar n ta yangi element kiritilsa, eng yomon xolatda algoritm bajarilishi quyidagicha o’rinlashtirishlar bajariladi, solishtirishlar ham xuddi shunday :