Bajardi: buronov umid qabul Qildi: Isroilov Sh Samarqand -2022 Heap tree tuzulmasi va ustida amallar bajarish algoritmlari
Download 238.64 Kb.
|
BURONOV UMID
- Bu sahifa navigatsiya:
- KIS20-01 GURUHI TALABASINING OPERATSION TIZIMLAR FANIDAN MUSTAQIL ISH Bajardi: BURONOV UMID Qabul Qildi: Isroilov Sh
- Binary Heap ma’lumotlar to’plami
- Binary heap nima uchun kerak
- Kodda ifodalash
O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI SAMARQAND FILIALI KOMPYUTER INJINIRINGI FAKULTETI KIS20-01 GURUHI TALABASINING OPERATSION TIZIMLAR FANIDAN MUSTAQIL ISHBajardi: BURONOV UMID Qabul Qildi: Isroilov Sh Samarqand -2022 Heap tree tuzulmasi va ustida amallar bajarish algoritmlari Reja : I.Kirish II. Asosiy qism. 1. Binary Heap ma’lumotlar to’plami. 2. Tree ma’lumotlar tuzilmasi. III.Xulosa : IV.Foydalanilgan adabiyotlar : Binary Heap ma’lumotlar to’plami Binary heap – har bir tuguni (node) maxsus tartiblangan va complete binary tree. Binary heap bo’lishi uchun tree’da ma’lumotlar shajara bo’yicha o’sish tartibida (max heap) yoki kamayish tartibida (min heap) joylashgan bo’lishi kerak. 1.Max-Heap bo’lishi uchun har bir node’ning qiymati uning parent node’ining qiymatidan kichik yoki teng bo’lishi kerak. Eng katta qiymat root’da bo’ladi. Qoida tree’dagi barcha node’lar uchun amal qiladi. 2.Min-Heap bo’lishi uchun har bir node’ning qiymati uning parent node’ining qiymatidan katta yoki teng bo’lishi kerak. Eng kichkina qiymat root’da bo’ladi. Qoida tree’dagi barcha node’lar uchun amal qiladi. Max Heap va Min Heap Binary heap nima uchun kerak? Qisqa javob – heap’dagi eng katta (yoki eng kichik) elementni topish uchun kerak. Bunda binary heap tuzilishi tree bo’lgani uchun eng pastki elementdan eng yuqori elementga chiqish uchun O (log N) urinish lozim. Masalan yuqoridagi rasmda har bir tree’da 7 ta node bo’lsa, pastdan yuqoriga chiqish – log27 = 2.8 ~ 2 ta urinishda bo’ladi. Priority queue maqolasida biz ro’yhatdan eng katta va eng kichik elementni topishni ko’rgan edik. Uning kamchiligi – tartiblanmagan array uchun eng katta (yoki eng kichik) elementni topishda time complexity O(N) bo’lib ketayotgan edi. Tartiblangan array uchun esa, eng katta (eng kichik) elementni topish O(1) bo’ladi, lekin bunda array element qo’shganimizda har safar array’ni tartiblashga majbur bo’linardi – O(N log N). Demak, Binary heap Priority queue’dan ko’ra samaraliroq ishlaydi. Qo’shish va o’chirish – binary tree’dagi kabi O (log N). Binary heap’ning kamchiligi – u faqat eng katta (eng kichkina) elementlarni tezda topish imkonini beradi. Boshqa qiymatdagi elementlarni topish uchun heapni «titkilab» chiqish kerak. Sababi binary heap – tartiblanmagan. Tabiiyki tartiblanmagan ro’yhatdan qidirish O(N) vaqtni oladi. Masalan yuqoridagi rasm’dan 30 sonini topish uchun heap’ning hamma elementlari tekshirib chiqish kerak bo’ladi. Kodda ifodalash Binary heap uchun double pointer’li linked list ishlatish shartmas. Shunchaki array bilan ham ifodalasa bo’ladi. Amallar osonroq bo’lishi uchun array[0] ni bo’sh qoldiramiz, keyin heap qiymatlarini kiritamiz. Bizda Max heap’ni kodda ifodalash Download 238.64 Kb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling