Binary heap nege kerek?

Binary heap nege kerek?
Binary Heap-heapdag’i’ eń úlken (yamasa eń kishi) elementti tabıw ushın kerek. Bunda binary heap dúzilisi tree bolǵanı ushın eń tómengi elementten eń joqarı elementke shıǵıw ushın O (log N) ma’rte urınıw kerek. Mısalı joqarıdaǵı suwretde hár bir tree'da 7 node bolsa, tómennen joqarıǵa shıǵıw - log27 = 2. 8 ~ 2 ma’rte urınıwda boladı.
Ekilik terek - bul hár bir ata-ana ushın eń kóp eki balaǵa iye bolǵan terek tipindegi sızıqlı bolmaǵan maǵlıwmatlar strukturası. Ekilik terektegi hár bir túyin maǵlıwmatlar elementi menen birge shep hám oń uyqas jazıwlarǵa iye. Terek ierarxiyasini’n’ joqarı bólegindegi túyin túbir túyin dep ataladı. Basqa kishi túyinlerdi ustap turatuǵın túyinler ata-ana túyinleri bolıp tabıladı.
Ata-ana túyininde eki túyin ámeldegi: shep hám oń túyin. Xeshlew, tarmaq trafigi ushın maǵlıwmatlardı marshrutlaw, maǵlıwmatlardı qısıw, ekilik toplardı tayarlaw hám ekilik izlew terekleri ekilik terekten paydalanatuǵın birpara qosımshalar bolıp tabıladı.
Ekilik terekler menen baylanıslı atamalar hám ekilik tereklerdiń túrleri
Túyin: Bul terektegi tamamlaw noqatın ańlatadı.
Túbir: Terektiń eń joqarı túyinleri.
Ata-ana: Terektegi hár bir túyin (túbirden tısqarı) keminde bir kishi túyinge iye bolǵan ana túyin dep ataladı.
Child: Túbirden uzaqlasqanda tezlik penen ata-ana túyininen kelgen túyin - bul túyin.
Japıraq túyinleri: Bular sırtqı túyinler bolıp tabıladı. Olar balası bolmaǵan túyinler bolıp tabıladı.
Ishki túyin: Atınan kórinip turıptı, olda, bular keminde bir balalı ishki túyinler bolıp tabıladı.
Terektiń tereńligi: terek túyininen túbirge shekem bolǵan qırlardıń sanı.
Terektiń biyikligi: Bul túyinnen eń tereń japi’raqqa shekem bolǵan qırlardıń sanı. Terek biyikligi de túbir biyikligi esaplanadı.
Ekilik terek hám ekilik terek túrleri menen baylanıslı terminologiyalar menen tanıs bolǵanıńız ushın, ekilik terek komponentlerin túsiniw waqtı keldi. Ekilik struktura hám komponentler haqqında tereńrek úyreniw ushın maǵlıwmatlar pánleri kurslari’mi’zdi’ kórip shıǵıń.
Ekilik terektiń ush komponenti bar. Hár bir binar terek túyininde ol menen baylanısqan bul ush komponent bar. Bul ush ekilik terek komponentlerin túsiniw programmistler ushın zárúrli túsinikke aylanadı :
Maǵlıwmatlar elementi
Kórsetkish shep tómengi terekke
Oń tómengi terekke kórsetkish

Bul ush ekilik terek komponentleri túyindi ańlatadı. Maǵlıwmatlar ortada jaylasqan. Shep kórsetkish shep tómengi terekti quraytuǵın bala túyinine belgi etedi. Tuwrı kórsetkish ońı daǵı bala túyinine belgi etip, tuwrı tómengi terekti jaratadı.

Oqiń: Maǵlıwmatlar pániniń tiykarǵı sorawları hám informatsion usılları
Ekilik tereklerdiń túrleri
Ekilik tereklerdiń hár túrlı túrleri ámeldegi jáne bul ekilik terek túrleriniń hár biri ayriqsha ayrıqshalıqlarǵa iye. Ekilik terek túrleriniń hár biri tolıq :
1. Tolıq ekilik terek
Bul nol yamasa eki balaǵa iye bolǵan ekilik terektiń arnawlı túri. Bul sonı ańlatadıki, bul ekilik terektegi barlıq túyinler yamasa ata-ana túyininiń eki tiykarǵı túyinine ıyelewi kerek yamasa ata-ana túyininiń ózi japıraq túyin yamasa sırtqı túyin bolıp tabıladı.
Basqasha etip aytqanda, tolıq ekilik terek kem ushraytuǵın ekilik terek bolıp, sırtqı túyinnen tısqarı hár bir túyin eki balaǵa iye. Bir balanı ustap turǵanda, bunday ekilik terek tolıq ekilik terek bolmaydı. Bul erda japıraq túyinleriniń muǵdarı ishki túyinler sanına plyus birge teń. Teńleme L=I+1 ge uqsaydı, bul erda L - japıraq túyinleri sanı, I - ishki túyinler sanı.
Mine tolıq binar terektiń dúzilisi:

2. Tolıq ekilik terek

Tolıq ekilik terek - bul ekilik terektiń taǵı bir ayriqsha túri bolıp, ol jaǵdayda terektiń eń tómen dárejesinden tısqarı barlıq terek dárejeleri pútkilley túyinler menen toldırılǵan. Bunnan tısqarı, bul ekilik terektiń aqırǵı yamasa eń tómen dárejesinde hár bir túyin shep tárepte jaylasqan bolıwı kerek. Mine, tolıq ekilik terektiń dúzilisi:

3. Jetilisken ekilik terek

Ekilik terek " jetilisken" dep aytıladı, eger barlıq ishki túyinler qatań eki balaǵa iye bolsa hám hár bir sırtqı yamasa japıraq túyinleri terek ishinde birdey dárejede yamasa birdey urada bolsa. “H” biyikligine iye bolǵan jetilisken ekilik terek 2 h - 1 túyinge iye. Mine jetilisken ekilik terektiń dúzilisi:

4. Balanslanǵan ekilik terek

Ekilik terek " teń salmaqlılıqlangan" dep ataladı, eger terek biyikligi O (logN) bolsa, bul erda " N" - túyinler sanı. Balanslanǵan ekilik terekte hár bir túyindiń shep hám oń tómengi terekleriniń biyikligi kópi menen birdey bolıwı kerek. AvL tereki hám qızıl -qara terek teń salmaqlılıqlı ekilik qıdırıw terekin jaratılıwması múmkin bolǵan maǵlıwmatlar strukturasınıń birpara ulıwma mısalları bolıp tabıladı. Mine teń salmaqlılıqlı ekilik terekke mısal :

5. Ekilik terektiń degeneratsiyasi

Eger hár bir ishki túyinde tek bir bala bolsa, ekilik terek degeneratsiyalangan ekilik terek yamasa patologikalıq binar terek dep ataladı. Bunday terekler islew tárepinen baylanısqan dizimge uqsaydı. Mine buzılǵan ekilik terekke mısal :

Ekilik terektiń abzallıqları

Ekilik terekte qıdırıw operatsiyası basqa tereklerge qaraǵanda tezirek
Elementlerdi tártiplengen tártipte támiyinlew ushın tek eki ótiw jetkilikli
Maksimal hám minimal elementlerdi tańlaw ańsat
Grafik ótiwde ekilik terekler de qollanıladı
Ekilik terekler járdeminde túrli postfiks hám prefiks ańlatpaların aylandırıw múmkin
Juwmaq
Ekilik terek maǵlıwmatlar strukturasında eń kóp qollanılatuǵın tereklerden biri bolıp tabıladı. Ekilik terek túrleriniń hár biri ayriqsha ayrıqshalıqlarǵa iye. Bul maǵlıwmatlar strukturaları ámeliy kompyuter páninde ayriqsha talaplarǵa iye. Ekilik tereklerdiń túrleri haqqında bul maqala paydalı boldı dep úmit etemiz. upGrad maǵlıwmatlar pánleri, mashinalardı úyreniw, úlken maǵlıwmatlar hám basqalar boyınsha túrli kurslardı usınıs etedi.