heap treetuzilmasitavsifi

PPTX 28 sahifa 2,0 MB Bepul yuklash

28 sahifa

FaylHub.uz

Telegram orqali yuklab olish

Hajm 2,0 MB

Fayl turi PPTX

Sahifalar 28

Yangilangan Dek 2025

Sahifa ko'rinishi (5 sahifa)

Pastga aylantiring 👇

1 / 28

10 – mavzu. heap tree ko’rinishidagi binar daraxtlarni qurish algoritmi va ular ustida amallar heaps qonuni reja: 1. heaps qonuni va tree tuzilmasi tavsifi. 2. heap tree ustida amal bajarish algoritmlari. 3. heap treeni tashkil etish usullari va samaradorligi. heaps qonuni m sonini baholash uchun heaps qonunidan foydalanish afzal. chunki unda ma’lumotlar to’plami bilan bog’liq funksiyalar foydalaniladi. m = . (1) bu yerda t – to’plamdagi so’zlar soni, k va b lar tipik parametrlar qiymati 30 ≤ k ≤100 va b ≈ 0.5. heaps qonunining muhimligi to’plam va lug’at hajmining o’zaro munosabati oddiy chiziqli funksiya orqali logrifmik koordinatalar tizimi keltirilganligidir (3-rasm). ushbu holatda t< =100000 bo’lganda b = 0.49 va k=44 mos keladi. masalan, birinchi 100020 so’z uchun heaps qonuni asosida terminlar soni 38323ta, ammo aslida terminlar soni 38365 taga tengdir (bir-biriga juda yaqin qiymatlar). 44×38323. heaps qonuni heap tree tuzilmasi tavsifi heap tree so’zi inglizchadan olingan bo’lib, ikkilik uyurma …

2 / 28

bo’lsin. undan yuqoridan pastga va chapdan o’ngga elementlarni joylab daraxtni (heap tree bo’lmagan) xosil qilamiz. bunday daraxtlarda bosqichlar soni o(lgn) gat eng. 10.2-rasm. massivdan daraxt xosil qilish bu daraxtni heap tree ko’rinishida qayta tashkil etish uchun uzunligi n ga teng heap massivini quyidagi shartlarga asoslanib tashkil etamiz: heap[i] ≥ heap[2·i], for 0 ≤ i< va heap[i] ≥ heap[2·i + 1], for 0 ≤ i< heap tree elementlari tartiblanmagan hisoblanadi. boshqacha qilib aytadigan bo’lsak, sonlar ketma-ketligidan heap treeni qurish uchun 1-elementni daraxt ildizi qilib olamiz. har qanday i-element uchun quyidagi o’rinli: uning chap o’g’il tuguni 2*i indeksda o’ng o’g’il tuguni esa 2*i+1 indeksda uning ota tuguni i/2 indeksda bo’ladi. 10.3-rasm. heap tree ya’ni 1-elementni ildiz qilib olgach, qolgan elementlarni chapdan o’ngga qarab daraxtni to’ldirib ketiladi. xar bir ildizda faqat ikkita o’g’il tugun chiqishi kerak. agar shunday tartibda elementlar joylashtirilib chiqadigan bo’lsa, xar bir a[i]-o’rinda turgan ota tugunning chap tomoniga a[2*i]-element va …

3 / 28

lementni 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, 10.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 …

4 / 28

onidan taklif etilgan. quyida rasmda “tepadan-pastga” algoritmi ifodalangan va dasturi keltirilgan. 10.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. (10.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); 10.7-rasm. array[2 8 6 1 10 15 3 12 11] …

5 / 28

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. e’tiboringiz uchun raxmat ! image2.emf image3.png image3.emf image4.png image5.png image50.png image6.png image7.png image8.png image9.png image10.png image11.png image12.png image13.png image14.png image15.png image16.png image17.png image18.png image19.png image20.png image21.png image1.jpg /docprops/thumbnail.jpeg

Ko'proq o'qimoqchimisiz?

Barcha 28 sahifani Telegram orqali bepul yuklab oling.

To'liq faylni yuklab olish

"heap treetuzilmasitavsifi" haqida

10 – mavzu. heap tree ko’rinishidagi binar daraxtlarni qurish algoritmi va ular ustida amallar heaps qonuni reja: 1. heaps qonuni va tree tuzilmasi tavsifi. 2. heap tree ustida amal bajarish algoritmlari. 3. heap treeni tashkil etish usullari va samaradorligi. heaps qonuni m sonini baholash uchun heaps qonunidan foydalanish afzal. chunki unda ma’lumotlar to’plami bilan bog’liq funksiyalar foydalaniladi. m = . (1) bu yerda t – to’plamdagi so’zlar soni, k va b lar tipik parametrlar qiymati 30 ≤ k ≤100 va b ≈ 0.5. heaps qonunining muhimligi to’plam va lug’at hajmining o’zaro munosabati oddiy chiziqli funksiya orqali logrifmik koordinatalar tizimi keltirilganligidir (3-rasm). ushbu holatda t< =100000 bo’lganda b = 0.49 va k=44 mos keladi. masalan, birinchi 100020 so’z uchun heaps qonuni …

Bu fayl PPTX formatida 28 sahifadan iborat (2,0 MB). "heap treetuzilmasitavsifi"ni yuklab olish uchun chap tomondagi Telegram tugmasini bosing.

Teglar: heap treetuzilmasitavsifi PPTX 28 sahifa Bepul yuklash Telegram