|
Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti nurafshon filiali "Axborot texnologiyalari" kafedrasi Guruh: 610-21 Talaba: Muhammadjonov Sodiqjon Rahbar: Tosheva Muhabbat
|
| Sana | 26.04.2023 | | Hajmi | 13.51 Mb. | | #53958 |
Bog'liq MTA SODIQJON CAE 2 Book, МАРКЕТИНГ мустақил иш, Eratosfen, Eratosfe2, 692-qaror MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI NURAFSHON FILIALI "Axborot texnologiyalari" kafedrasi Guruh: 610-21 Talaba: Muhammadjonov Sodiqjon Rahbar:Tosheva Muhabbat Mavzu: Heap tree ko’rinishidagi binar daraxtlarni qurish algoritmi va ular ustida amallar. 1. Heap tree tuzilmasi tavsifi. 2. Heap tree ustida amal bajarish algoritmlari. 3. Heap treeni tashkil etish usullari va samaradorligi.
Heap tree so’zi inglizchadan olingan bo’lib, ikkilik uyurma daraxti degan ma’noni anglatadi va binar daraxtning bir turi bo’lib, binar daraxtdan quyidagi ikkita xususiyati bilan ajralib turadi.
- Har bir tugun qiymati uning o’g’il tugunlari qiymatidan katta yoki teng (yoki kichik yoki teng bo’lishi ham mumkin);
- Daraxt ideal muvozanatlangan, yoki daraxt barg tugunlari chapdan o’ngga qarab to’ldiriladi.
- Agar xar bir tugun o’g’il tugunlatdan katta yoki teng bo‘lsa, bu uyurma daraxtiga max heap, aks holda ya’ni ota tugun farzandlardan kichik yoki teng bo’lsa, min heap deyiladi. Bu degani, max heap da maksimal element daraxt ildizida joylashadi, min heapda esa daraxtning ildizida minimal element joylashadi.
- Heap tree (a) va heap tree bo’lmagan daraxtlar Bu yerda rasmdagi a) heap tree va b),c) lar esa heap tree emas. Chunki b va c rasmda heap treening birinchi va ikkinchi xususiyatlari buzilgan mos ravishda. Qizig’I shuki, heap tree massiv yordamida yasalishi mumkin. Masalan, data[] = {2 8 6 1 10 15 3 12 11} massiv berilgan 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.
Binar uyum (binary heap) bu quyidagi shartlarni qanoatlantiradigan binar daraxtdir: - Har qanday uchning ustivorligi, uning avlodlarining ustivorligidan kichik emas. - Daraxt to'liq ikkilik daraxt boʻlishi uchun (complete binary tree) -barcha darajalar chapdan o'ngga to'ldiriladi.
1
O'smaydigan piramida
max-heap
Har qanday uchning ustuvorligi avlodlaming ustuvorligidan kichik emas
2
Kamaymaydigan piramida
min-heap
Har qanday uchning ustuvorligi avlodlarning ustuvorligidan katta emas
Bo‘sh uyum (kucha) hosil qilish
stmct heap *heap_create(int niaxsize)
{
stnict heap *h;
h = malloc(sizeof(*h));
if(h !=NULL)
{
h->maxsize = maxsize;
h->nnodes = 0;
/* Heap nodes [0. 1. maxsize] */
h->nodes = malloc(sizeof(*h->nodes) * (maxsize + 1)); if (h->nodes = NULL) {
free(h);
retumNULL;
}
retum h;
Uyumni o‘chirish
void heap_free(struct heap *h)
{
free(h->nodes);
free(h);
}void heap_swap(struct heapnode *a, struct heapnode *b)
{struct heapnode temp;
temp = *a;
*a = *b;
struct heapnode *heap_max(struct heap *h {
if (h->nnodes == 0)
return NULL;
return &h->nodes[l];
E’tiboringiz uchun rahmat! E’tiboringiz uchun rahmat!
|
|
Bosh sahifa
Aloqalar
Bosh sahifa
Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti nurafshon filiali "Axborot texnologiyalari" kafedrasi Guruh: 610-21 Talaba: Muhammadjonov Sodiqjon Rahbar: Tosheva Muhabbat
|
