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


Heap tree tuzilmasi bilan ishlash samaradorligi



Download 18,83 Mb.
bet83/225
Sana30.12.2021
Hajmi18,83 Mb.
#89889
1   ...   79   80   81   82   83   84   85   86   ...   225
Bog'liq
“MTA” fani boyicha oquv uslubiy qollanma

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.


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.

Robert Floyd tomonidan taklif etilgan boshqa bir algoritmda heap tree “pastdan-yuqoriga” usuli yordamida amalga oshiriladi. Bunda kichik heap qismlar yaratiladi va davriy ravishda kattaroq heaplarga birlashtiriladi. (11.7-rasm)

(quyidagi listingda keltirilgan moveDown() funksiyasi ildizdagi elementlarni quyiga xarakat qildiradi.)

FloydAlgorithm(data[])

for i = index of the last nonleaf down to 0

restore the heap property for the tree whose root is data[i] by calling

moveDown(data,i,n-1);

13.7-rasm. Array[2 8 6 1 10 15 3 12 11] massivni “pastdan-yuqoriga” usuli bilan heap treega aylantirish.

Bunda elementlarni tekshirish data[n/2-1] barg tugun bo’lmagan elementdan boshlaymiz. Agar u o’g’il tugunlarining birontasidan kichik bo’lsa, katta qiymatli o’g’il element bilan almashtiriladi va jarayon yuqoridagi rasmdagi kabi davom ettiriladi. Bu usulda qachonki yangi element tahlil qilinayotganda uning qism daraxti allaqachon heap bo’ladi. Shunday qilib, heap tree pastdan yuqoriga qarab shakllantiriladi. Heapni bunday taskil qilishda, moveDown() funksiyasi (n+1)/2 marta chaqiriladi, xar bir barg bulmagan tugun uchun. Eng yomon holatda moveDown() elementni (n+1)/4 ta elementdan iborat bo’lgan eng quyi bosqishga ko’chiradi, bunda barg tugunlar bosqichiga yetib kelguncha xar bir bosqichda (n+1)/4 ta o’rinlashtirishlarni amalga oshiradi.

Qisqasi, bu usul samaradorligi O(n) gat eng. Shu sababli eng o’g’ir holatda Williamning usuli Floydning usulidan samaraliroq hisoblanadi. O’rta holatda esa ikkala algoritm ham deyarli bir xil.



Download 18,83 Mb.

Do'stlaringiz bilan baham:
1   ...   79   80   81   82   83   84   85   86   ...   225




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish