Dvejetainės krūvos ir prioritetinės eilės
Dvejetainė maksimumo krūva masyve saugo dvejetainį medį, kurio visi lygiai, išskyrus galbūt paskutinį, užpildyti, o paskutinio lygio viršūnės išdėstytos iš kairės į dešinę be tarpų; kiekvienos tėvinės viršūnės raktas yra ne mažesnis už jos vaikų raktus.
Esminės žinios
Dvejetainėje maksimumo krūvoje masyve saugomas dvejetainis medis, kurio visi lygiai, išskyrus galbūt paskutinį, užpildyti, o paskutinio lygio viršūnės išdėstytos iš kairės į dešinę be tarpų; kiekvieno tėvinio mazgo raktas yra ne mažesnis už jo vaikinių mazgų raktus. Maksimumo paieškos trukmė yra O(1); krūvos tvarkos atkūrimas aukštyn arba žemyn po įterpimo ar pašalinimo trunka O(log n), o krūvos sudarymas iš apačios į viršų – O(n).
Sąlygos ir taikymo ribos
- Krūvos tvarka nesurikiuoja visų raktų.
- Minimumo krūvai naudokite analogiškus priešingos krypties palyginimus.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Paskaita 8: krūvos savybė, krūvos tvarkos atkūrimo operacijos ir tiesinio sudarymo laiko analizė.
2026-10-10 · Nepriklausoma DI redakcinė peržiūra: perskaityti visi glaustai suformuluoti teiginiai (241), hipotezės, pateiktos lygtys ir susitarimai bei visos kilmės semantinės sąsajos (596); peržiūrėta visa autoriaus sudaryta 241 įrašo tikslių šaltinių patikros matrica ir deklaruoti apribojimai. Siekiant aprėpti visą įrašų rinkinį, perskaityti 105 ankstesni faktiškai paveldėti matematikos ir informacijos įrašai. Toliau išvardyti tikslingai ir nepriklausomai peržiūrėti pirminių šaltinių skyriai; tuo NETEIGIAMA, kad kiekvieno cituojamo šaltinio visas tekstas ar kiekvienas įrodymas buvo nepriklausomai perskaitytas iš naujo. Tai DI atlikta informacinio turinio peržiūra, o ne žmogaus eksperto patvirtinimas atitinkamoje mokslo srityje, išsamus vadovėlio atkūrimas ar eksperimentinis pakartojimas. Peržiūros įrašas: mathematics-information-independent-content-review.1.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-binary-heaps
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra