Phenquestions
Krūvos duomenų struktūrų iliustracija
Yra dviejų rūšių kaupai: „max-heap“ ir „min-heap“. „Max-heap“ struktūra yra ta vieta, kur didžiausia reikšmė yra šaknis, o vertės mažėja, kai medis nusileidžia; bet kurio iš tėvų vertė yra lygi arba didesnė už bet kurį iš artimiausių vaikų. Min-heap struktūra yra ta vieta, kur minimali reikšmė yra šaknis, o reikšmės tampa didesnės, kai medis nusileidžia; bet kurio iš tėvų vertė yra lygi arba mažesnė už bet kurį iš artimiausių vaikų. Šiose diagramose pirmasis yra „max-heap“, o antrasis - „min-heap“:
Abiejų kaupų atveju atkreipkite dėmesį, kad porai vaikų nėra svarbu, ar kairėje esanti vertė yra didesnė. Eilutė medžio lygyje nebūtinai turi būti užpildyta nuo mažiausio iki didžiausio iš kairės; jis taip pat nebūtinai užpildomas iš didžiausio į minimalų, iš kairės.
Atstovaudamas krūvą masyve
Kad programinė įranga galėtų lengvai naudoti krūvą, krūvą reikia pateikti masyve. Aukščiau esantis maksimalus kaupas, pateiktas masyve, yra:
89, 85, 87, 84, 82, 79, 73, 80, 81,, 65, 69Tai daroma pradedant nuo šaknies vertės kaip pirmosios masyvo vertės. Vertės nuolat dedamos skaitant medį iš kairės į dešinę, iš viršaus į apačią. Jei elemento nėra, jo padėtis masyve praleidžiama. Kiekviename mazge yra du vaikai. Jei mazgas yra indekso (padėties) n vietoje, jo pirmasis antrasis masyvo indeksas yra 2n + 1, o kitas vaikas yra indekse 2n + 2. 89 yra 0 indekse; jo pirmasis vaikas, 85 yra 2 rodyklėje (0) + 1 = 1, o antrasis vaikas - 2 (0) + 2 = 2. 85 yra 1 rodyklėje; jos pirmasis vaikas, 84 m., yra 2 (1) + 1 = 3, o antrasis 82 m. - 2 (1) + 2 = 4. 79 yra 5 rodyklėje; jo pirmasis vaikas, 65, yra 2 (5) + 1 = 11, o antrasis vaikas - 2 (5) + 2 = 12. Formulės taikomos likusiems masyvo elementams.
Toks masyvas, kai elemento reikšmę ir santykį tarp elementų reiškia elemento padėtis, vadinamas implicitine duomenų struktūra.
Netiesioginė minėto krūvos duomenų struktūra yra:
65, 68, 70, 73, 71, 83, 84,, 79, 80,, 85, 89Aukščiau pateiktas maksimalus krūva yra visas dvejetainis medis, bet ne visas dvejetainis medis. Štai kodėl kai kurios vietos (pozicijos) masyve yra tuščios. Jei naudojate visą dvejetainį medį, masyve jokia vieta nebus tuščia.
Dabar, jei krūva būtų beveik baigtas medis, pavyzdžiui, jei trūktų vertės 82, masyvas būtų:
89, 85, 87, 84, 79, 73, 80, 81,, 65, 69Šioje situacijoje trys vietos yra tuščios. Tačiau formulės vis dar taikomos.
Operacijos
Duomenų struktūra yra duomenų formatas (pvz.,.g. medis), plius santykis tarp reikšmių ir operacijos (funkcijos), atliekamos su vertėmis. Krūvos atveju santykis, einantis per visą krūvą, yra tas, kad tėvai turi būti lygūs ar didesni už vaikus, kad būtų galima gauti didžiausią krūvą; o tėvas turi būti lygus ar mažesnis už vaikus, kad gautų min-krūvą. Šie santykiai vadinami krūvos nuosavybe. Krūvos operacijos sugrupuotos po kūrimo, pagrindinio, vidinio ir tikrinimo skiltimis. Toliau pateikiama krūvos operacijų santrauka:
Krūvos operacijų suvestinė
Yra tam tikros programinės įrangos operacijos, būdingos kaupams, taip:
Krūvos sukūrimas
create_heap: Sukurti krūvą reiškia suformuoti objektą, kuris reprezentuoja krūvą. C kalba galite sukurti kaupą naudodami struktūros objekto tipą. Vienas iš struktūros narių bus krūvos masyvas. Likę nariai bus krūvos funkcijos (operacijos). „Create_heap“ reiškia tuščio kaupo sukūrimą.
„Heapify“: kaupo masyvas yra dalinai surūšiuotas (užsakytas) masyvas. „Heapify“ reiškia pateikti krūvų masyvą iš nerūšiuoto masyvo - žr. Išsamią informaciją toliau.
Sujungti: tai reiškia, kad iš dviejų skirtingų kaupų suformuokite sąjungos kaupą - žr. Išsamią informaciją toliau. Abu kaupai turėtų būti maksimalūs arba abu su kaupu. Naujasis krūva atitinka savybę su kaupu, o originalūs kaupai yra išsaugoti (neištrinti).
Susiliejimas: Tai reiškia, kad sujunkite du to paties tipo kaupus ir suformuokite naują, išlaikydami dublikatus - žr. Išsamią informaciją toliau. Naujasis krūva atitinka kaupo savybę, o pradiniai kaupai yra sunaikinti (ištrinti). Pagrindinis skirtumas tarp sujungimo ir suliejimo yra tas, kad suliejimui vienas medis tinka kaip antras medis prie kito medžio šaknies, leidžiantis pasikartojančias reikšmes naujame medyje, o sujungiant suformuojamas naujas krūvos medis, pašalinant dublikatus. Nereikia išlaikyti dviejų originalių kaupų su lydymu.
Pagrindinės krūvos operacijos
find_max (rasti_min): raskite maksimalaus masyvo masyvo didžiausią vertę ir grąžinkite kopiją arba suraskite mažiausią masyvo masyvo vertę ir grąžinkite kopiją.
Įterpti: pridėkite naują elementą prie kaupo masyvo ir pertvarkykite masyvą taip, kad išlaikytų diagramos savybę.
extract_max (extract_min): raskite maksimalaus masyvo maksimalią vertę, pašalinkite ir grąžinkite; arba raskite mažiausią vertę „min-heap“ masyve, pašalinkite ir grąžinkite.
delete_max (delete_min): suraskite „max-heap“ šakninį mazgą, kuris yra pirmasis „max-heap“ masyvo elementas, pašalinkite jį nebūtinai grąžindamas; arba suraskite „min-heap“ šaknies mazgą, kuris yra pirmasis „min-heap“ masyvo elementas, pašalinkite jį nebūtinai grąžindami;
Pakeisti: Suraskite bet kurio krūvos šaknies mazgą, pašalinkite jį ir pakeiskite nauju. Nesvarbu, ar grąžinama senoji šaknis.
Vidaus kaupo operacijos
padidinti_ raktą (sumažinti_ raktą): Padidinkite bet kurio „max-heap“ mazgo vertę ir pertvarkykite taip, kad būtų išlaikyta „heap“ savybė, arba sumažinkite bet kurio „min-heap“ ir „pertvarkymo“ mazgo vertę, kad išlaikytų „heap“ ypatybę.
Ištrinti: ištrinkite bet kurį mazgą, tada pertvarkykite, kad būtų išsaugota „heap“ savybė „max-heap“ arba „min-heap“.
„shift_up“: perkelkite mazgą į viršų „max-heap“ arba „min-heap“ tiek, kiek reikia, pertvarkydami, kad išlaikytumėte „heap“ savybę.
shift_down: perkelkite mazgą žemyn max-heap ar min-heap tiek ilgai, kiek reikia, pertvarkykite, kad išlaikytumėte krūvos savybę.
Krūvos apžiūra
Dydis: Tai grąžina krūvos raktų (verčių) skaičių; jame nėra tuščių kaupo masyvo vietų. Krūva gali būti pavaizduota kodu, kaip diagramoje, arba su masyvu.
Yra tuščias: Tai grąžina Bulio reikšmę teisinga, jei kaupe nėra mazgo, arba netikslią reikšmę, jei kaupe yra bent vienas mazgas.
Sijojimas su kaupu
Yra persijojimas ir atsijojimas:
Perkėlimas: Tai reiškia, kad pakeiskite mazgą su savo tėvais. Jei krūvos savybė nėra patenkinta, pakeiskite tėvus su savo tėvais. Toliau važiuokite šiuo keliu, kol bus patenkinta savybė. Procedūra gali pasiekti šaknį.
Perkelti žemyn: Tai reiškia, kad pakeiskite didelės vertės mazgą mažesniuoju iš dviejų savo vaikų (arba vienu vaiku į beveik visą krūvą). Jei krūvos savybė nėra patenkinta, pakeiskite apatinį mazgą mažesniuoju savo dviejų vaikų mazgu. Toliau eikite šiuo keliu, kol bus patenkinta savybė. Procedūra gali pasiekti lapą.
Kupinanti
„Heapify“ reiškia rūšiuoti nerūšiuotą masyvą, kad krūvos savybė būtų patenkinta „max-heap“ arba „min-heap“. Tai reiškia, kad naujajame masyve gali būti tuščių vietų. Pagrindinis algoritmas, skirtas kaupti „max-heap“ arba „min-heap“, yra toks:
- jei šaknies mazgas yra kraštutinesnis už bet kurį iš jo vaiko mazgų, tada pakeiskite šaknį su mažiau ekstremaliu vaiko mazgu.
- Pakartokite šį veiksmą su vaikų mazgais iš anksto užsisakydami medžių važiavimo schemą.
Galutinis medis yra krūvos medis, patenkinantis krūvos savybę. Krūva gali būti pavaizduota kaip medžio diagrama arba masyvas. Gautas krūva yra iš dalies išrūšiuotas medis, t.e. iš dalies surūšiuotas masyvas.
Informacija apie krūvos operaciją
Šiame straipsnio skyriuje pateikiama išsami informacija apie kaupo operacijas.
Krūvos detalių sukūrimas
sukurti_krūvą
Pažiūrėkite aukščiau!
kaupti
Pažiūrėkite aukščiau
sujungti
Jei kaupo masyvai,
89, 85, 87, 84, 82, 79, 73, 80, 81,, 65, 69ir
89, 85, 84, 73, 79, 80, 83, 65, 68, 70, 71yra sujungti, rezultatas be dublikatų gali būti,
89, 85, 87, 84, 82, 83, 81, 80, 79, 73, 68, 65, 69, 70, 71Šiek tiek atsijojus. Atkreipkite dėmesį, kad pirmajame masyve 82 neturi vaikų. Gautame masyve jis yra 4 rodyklėje; ir jo vietos indekse 2 (4) + 1 = 9 ir 2 (4) + 2 = 10 yra laisvos. Tai reiškia, kad naujoje medžių diagramoje taip pat nėra vaikų. Dviejų pradinių kaupų nereikėtų ištrinti, nes jų informacijos iš tikrųjų nėra naujame krūvoje (naujas masyvas). Pagrindinis to paties tipo kaupų sujungimo algoritmas yra toks:
- Sujunkite vieną masyvą su kito masyvo apačia.
- „Heapify“ pašalina dublikatus, užtikrindama, kad mazgai, kurie neturėjo vaikų pradinėse kaupose, vis dar neturėtų vaikų naujame krūvoje.
sulydyti
Dviejų to paties tipo kaupų (dviejų maks. Arba dviejų min.) Suliejimo algoritmas yra toks:
- Palyginkite du šaknies mazgus.
- Padarykite mažiau kraštutinę šaknį ir likusį jos medį (poskį), antrąjį kraštutinės šaknies vaiką.
- Pasiklydusį vaiką persijunkite dabar kraštutinio potemio šaknyje, kraštutiniame pomedyje žemyn.
Gautas krūva vis dar atitinka krūvos savybę, o pradiniai kaupai yra sunaikinti (ištrinti). Pirminius kaupus galima sunaikinti, nes visa jų turima informacija vis dar yra naujame krūvoje.
Pagrindinės krūvos operacijos
rasti_max (rasti_min)
Tai reiškia rasti maksimalaus masyvo masyvo didžiausią vertę ir grąžinti kopiją, arba rasti minimalią masės masyvo vertę ir grąžinti kopiją. Krūvos masyvas pagal apibrėžimą jau tenkina krūvos savybę. Taigi, tiesiog grąžinkite pirmo masyvo elemento kopiją.
Įdėti
Tai reiškia, kad į kaupo masyvą reikia įtraukti naują elementą ir pertvarkyti masyvą taip, kad diagramos krūvos savybė būtų išlaikyta (patenkinta). Algoritmas tai padaryti abiejų tipų kaupuose yra toks:
- Tarkime, kad visas dvejetainis medis. Tai reiškia, kad prireikus masyvas turi būti užpildytas tuščiomis vietomis. Bendras viso krūvos mazgų skaičius yra 1, 3 arba 7, arba 15, arba 31, ir tt.; vis padvigubinkite ir pridėkite 1.
- Įdėkite mazgą į tinkamiausią tuščią vietą pagal dydį, link kaupo galo (link kaupo masyvo pabaigos). Jei nėra tuščios vietos, tada pradėkite naują eilutę iš apačios kairėje.
- Jei reikia, persijokite, kol bus patenkinta savybė.
extract_max (extract_min)
Suraskite didžiausią vertę „max-heap“ masyve, pašalinkite ir grąžinkite; arba raskite mažiausią vertę „min-heap“ masyve, pašalinkite ir grąžinkite. Algoritmas išskleisti_max (extract_min) yra toks:
- Pašalinkite šaknies mazgą.
- Paimkite (pašalinkite) apatinį dešinįjį mazgą (paskutinį masyvo mazgą) ir padėkite prie šaknies.
- Atitinkamai atsijokite, kol krūvos savybės bus patenkintos.
delete_max (ištrinti_min)
Suraskite „max-heap“ šaknies mazgą, kuris yra pirmasis „max-heap“ masyvo elementas, pašalinkite jį nebūtinai grąžindami; arba suraskite „min-heap“ šakninį mazgą, kuris yra pirmasis „min-heap“ masyvo elementas, pašalinkite jį nebūtinai grąžindami. Šaknies mazgo ištrynimo algoritmas yra toks:
- Pašalinkite šaknies mazgą.
- Paimkite (pašalinkite) apatinį dešinįjį mazgą (paskutinį masyvo mazgą) ir padėkite prie šaknies.
- Atitinkamai atsijokite, kol krūvos savybės bus patenkintos.
pakeisti
Suraskite bet kurio krūvos šaknies mazgą, pašalinkite jį ir pakeiskite nauju. Nesvarbu, ar grąžinama senoji šaknis. Jei reikia, atsijokite žemyn, kol bus patenkinta savybė.
Vidaus kaupo operacijos
padidinti_raktą (sumažinti_raktą)
Padidinkite bet kurio „max-heap“ mazgo vertę ir pertvarkykite taip, kad būtų išlaikyta „heap“ savybė, arba sumažinkite bet kurio „min-heap“ mazgo vertę ir pertvarkykite taip, kad būtų išlaikyta „heap“ savybė. Atitinkamai persijokite aukštyn arba žemyn, kol bus patenkinta savybė.
Ištrinti
Pašalinkite dominantį mazgą, tada pertvarkykite taip, kad būtų išlaikyta krūvos savybė max-heap arba min-heap. Mazgo ištrynimo algoritmas yra toks:
- Pašalinkite dominantį mazgą.
- Paimkite (pašalinkite) apatinį dešinįjį mazgą (paskutinį masyvo mazgą) ir padėkite prie pašalinto mazgo rodyklės. Jei ištrintas mazgas yra paskutinėje eilutėje, tai gali būti nereikalinga.
- Atitinkamai persijokite aukštyn arba žemyn, kol bus patenkinta savybė.
„shift_up“
Perkelkite mazgą aukštyn maksimaliu ar mažu kaupu tol, kol reikia, pertvarkykite, kad išlaikytumėte krūvos savybę - išsijokite aukštyn.
shift_down
Perkelkite mazgą žemyn „max-heap“ arba „min-heap“ kiek įmanoma ilgiau, pertvarkykite, kad išlaikytumėte krūvos savybę - atsijokite žemyn.
Krūvos apžiūra
dydžio
Pažiūrėkite aukščiau!
Yra tuščias
Pažiūrėkite aukščiau!
Kitos krūvos klasės
Šiame straipsnyje aprašytą kaupą galima laikyti pagrindiniu (bendruoju) kaupu. Yra ir kitų kaupų klasių. Tačiau du dalykai, kuriuos turėtumėte žinoti toliau, yra Dvejetainis ir D-arų kaupas.
Dvejetainis kaupas
Dvejetainis kaupas yra panašus į šį pagrindinį kaupą, tačiau turi daugiau apribojimų. Visų pirma, dvejetainis krūva turi būti visas medis. Nepainiokite tarp pilno ir pilno medžio.
d-ary Heap
Dvejetainis krūva yra 2 arų krūva. Krūva, kurioje kiekviename mazge yra 3 vaikai, yra 3 arų krūva. Krūva, kur kiekviename mazge yra 4 vaikai, yra 4 arų krūva ir pan. D-ario krūva turi kitų apribojimų.
Išvada
Krūva yra visas arba beveik visas dvejetainis medis, kuris tenkina krūvos savybę. Krūvos savybė turi dvi alternatyvas: norint gauti maksimalų kaupą, tėvai turi būti lygūs ar didesni už tiesioginius vaikus; norint gauti mažą kaupą, tėvų vertė turi būti lygi ar mažesnė už artimiausius vaikus. Krūva gali būti pavaizduota kaip medis arba masyvas. Esant masyvui, šaknies mazgas yra pirmasis masyvo mazgas; ir jei mazgas yra indekse n, jo pirmasis masyvo vaikas yra indekse 2n + 1, o kitas vaikas yra indekse 2n + 2. Krūva turi tam tikras operacijas, kurios atliekamos masyve.
Chrys
