Vodič za strukturu podataka o hrpi

Podaci su skup vrijednosti. Podaci se mogu prikupljati i stavljati u red ili u stupac, u tablicu ili u obliku stabla. Struktura podataka nije samo smještaj podataka u bilo kojem od ovih oblika. U računanju je struktura podataka bilo koji od ovih formata, plus odnos između vrijednosti, plus operacije (funkcije) koje se izvode na vrijednostima. Prije dolaska ovdje trebali biste već imati osnovno znanje o strukturi podataka stabla, jer će se tamošnji pojmovi ovdje koristiti s malo ili nimalo objašnjenja. Ako nemate to znanje, pročitajte tutorial pod nazivom Vodič za strukturu podataka o drvetu za početnike na poveznici https: // linuxhint.com / tree_data_structure_tutorial_beginners /. Nakon toga nastavite čitati ovaj vodič.Struktura podataka hrpe je cjelovito ili gotovo potpuno binarno stablo, pri čemu je podređenost svakog čvora po vrijednosti jednaka ili manja od vrijednosti njegovog roditelja. Alternativno, to je takvo stablo u kojem je vrijednost roditelja jednaka ili manja od vrijednosti bilo kojeg od njegovih djece. Vrijednost (datum) stabla također se naziva ključem.

Ilustracija podataka o hrpi podataka

Postoje dvije vrste gomila: max-heap i min-heap. Struktura max-heap je gdje je maksimalna vrijednost korijen, a vrijednosti postaju sve manje kako se stablo spušta; bilo koji roditelj je ili jednak ili veći u vrijednosti od bilo koje od njegove neposredne djece. Min-heap struktura je tamo gdje je minimalna vrijednost korijen, a vrijednosti postaju veće kako se stablo spušta; bilo koji roditelj je ili jednak ili manji u vrijednosti od bilo kojeg od njegovih neposrednih djece. U sljedećim dijagramima, prva je max-heap, a druga min-heap:

Za obje hrpe imajte na umu da za par djece nije važno je li ono s lijeve strane veća vrijednost. Red u razini na drvetu, ne mora se nužno ispuniti od minimuma do maksimuma, slijeva; nije također nužno popunjen od maksimuma do minimuma, slijeva.

Predstavljanje hrpe u nizu

Da bi softver mogao lako koristiti hrpu, hrpa mora biti predstavljena u nizu. Gornja gomila, prikazana u nizu, je:

89, 85, 87, 84, 82, 79, 73, 80, 81,,, 65, 69

To se radi s početkom korijenske vrijednosti kao prve vrijednosti niza. Vrijednosti se kontinuirano postavljaju čitanjem stabla slijeva udesno, od vrha do dna. Ako je element odsutan, preskače se njegov položaj u polju. Svaki čvor ima dvoje djece. Ako je čvor na indeksu (položaju) n, njegovo je prvo dijete u nizu na indeksu 2n + 1, a njegovo sljedeće dijete na indeksu 2n + 2. 89 je na indeksu 0; njegovo prvo dijete, 85 ima indeks 2 (0) + 1 = 1, dok je njegovo drugo dijete indeks 2 (0) + 2 = 2. 85 je na indeksu 1; njegovo prvo dijete, 84, ima indeks 2 (1) + 1 = 3, dok je njegovo drugo dijete, 82, indeks 2 (1) + 2 = 4. 79 je na indeksu 5; njegovo prvo dijete, 65 ima indeks 2 (5) + 1 = 11, dok je njegovo drugo dijete indeks 2 (5) + 2 = 12. Formule se primjenjuju na ostale elemente niza.

Takav niz, gdje se značenje elementa i odnos između elemenata podrazumijeva položajem elementa, naziva se Implicitna struktura podataka.

Implicitna struktura podataka za gornju hrpu min:

65, 68, 70, 73, 71, 83, 84,,, 79, 80,,, 85, 89

Gornja max-hrpa je potpuno binarno stablo, ali ne i potpuno binarno stablo. Zbog toga su neka mjesta (položaji) u polju prazna. Za potpuno binarno stablo niti jedno mjesto neće biti prazno u polju.

Sada, ako je hrpa gotovo cjelovito stablo, na primjer, ako nedostaje vrijednost 82, onda bi niz bio:

89, 85, 87, 84,, 79, 73, 80, 81,,, 65, 69

U ovoj su situaciji tri mjesta prazna. Međutim, formule su i dalje primjenjive.

Operacije

Struktura podataka je format podataka (npr.g. stablo), plus odnos između vrijednosti, plus operacije (funkcije) koje se izvode nad vrijednostima. Za hrpu, odnos koji se proteže kroz cijelu hrpu je da roditelj mora biti jednak ili veći u vrijednosti od djece, za max hrpu; a roditelj mora biti jednak ili manji u vrijednosti od djece, za minimalnu hrpu. Taj se odnos naziva svojstvom hrpe. Operacije hrpe grupirane su pod naslovima Stvaranje, Osnovno, Interno i Inspekcija. Slijedi sažetak operacija hrpe:

Sažetak operacija hrpe

Postoje određene softverske operacije koje su uobičajene za hrpe, kako slijedi:

Stvaranje hrpe

create_heap: Stvaranje hrpe znači formiranje objekta koji predstavlja hrpu. U jeziku C možete stvoriti hrpu s tipom objekta struct. Jedan od članova strukture bit će niz hrpe. Ostatak članova bit će funkcije (operacije) za hrpu. Create_heap znači stvaranje prazne hrpe.

Heapify: Niz hrpe djelomično je sortiran (poredani) niz. Heapify znači, pružite niz hrpe iz nerazvrstanog niza - pogledajte detalje u nastavku.

Spajanje: To znači, formirajte gomilu sjedinjenja iz dvije različite hrpe - pogledajte detalje u nastavku. Dvije hrpe trebale bi biti max-heap ili obje min-heap. Nova hrpa u skladu je sa svojstvom hrpe, dok su izvorne hrpe sačuvane (ne brišu se).

Spojeno: To znači, spojite dvije hrpe istog tipa da biste formirali novu, zadržavajući duplikate - pogledajte detalje u nastavku. Nova hrpa u skladu je sa svojstvom hrpe, dok su izvorne hrpe uništene (izbrisane). Glavna razlika između spajanja i spajanja je u tome što se za stapanje jedno stablo uklapa kao podstablo u korijen drugog stabla, dopuštajući duplicirane vrijednosti u novom stablu, dok se za spajanje formira novo stablo hrpe uklanjajući duplikate. Nije potrebno održavati dvije izvorne hrpe spajanjem.

Osnovne operacije hrpe

find_max (find_min): Pronađite maksimalnu vrijednost u polju max-heap i vratite kopiju ili pronađite minimalnu vrijednost u polju min-heap i vratite kopiju.

Umetni: dodajte novi element u niz hrpe i preuredite niz tako da se zadrži svojstvo hrpe dijagrama.

extract_max (extract_min): Pronađite maksimalnu vrijednost u polju max-heap, uklonite je i vratite; ili pronađite minimalnu vrijednost u polju min-heap, uklonite je i vratite.

delete_max (delete_min): Pronađite korijenski čvor max-heap, koji je prvi element polja max-heap, uklonite ga bez nužnog vraćanja; ili locirajte korijenski čvor min-heap, koji je prvi element polja min-heap, uklonite ga bez nužnog vraćanja;

Zamjena: Pronađite korijenski čvor bilo koje hrpe, uklonite ga i zamijenite novim. Nije važno hoće li se vratiti stari korijen.

Interne operacije hrpe

povećati_ključ (smanjiti_ključ): Povećati vrijednost bilo kojeg čvora za max hrpu i preurediti tako da se zadrži svojstvo hrpe ili smanjiti vrijednost bilo kojeg čvora za min hrpu i preurediti tako da se zadržava svojstvo hrpe.

Delete: izbrišite bilo koji čvor, a zatim preuredite, tako da se zadržava svojstvo hrpe za max-heap ili min-heap.

shift_up: pomaknite čvor prema gore u max-heap ili min-heap koliko god je potrebno, preslagivanjem kako bi se održalo svojstvo hrpe.

shift_down: pomaknite čvor prema dolje u max-heap ili min-heap koliko god je potrebno, preslagivanjem kako bi se održalo svojstvo hrpe.

Pregled hrpe

Veličina: Ovo vraća broj ključeva (vrijednosti) u hrpi; ne uključuje prazna mjesta niza hrpe. Hrpa se može predstaviti kodom, kao na dijagramu, ili s nizom.

prazno je: Ovo vraća logičku vrijednost true ako u hrpi nema čvora ili logičku vrijednost false ako hrpa ima barem jedan čvor.

Prosijanje na hrpu

Postoji prosejavanje i sijanje dolje:

Prosijanje: To znači zamijeniti čvor s roditeljem. Ako svojstvo hrpe nije zadovoljeno, zamijenite roditelja s vlastitim roditeljem. Nastavite ovaj put u stazi dok se ne zadovolji svojstvo hrpe. Postupak može doći do korijena.

Prosijanje: To znači zamijeniti čvor velike vrijednosti s manjim od njegovo dvoje djece (ili jednim djetetom za gotovo kompletnu hrpu). Ako svojstvo hrpe nije zadovoljeno, zamijenite donji čvor s manjim čvorom vlastitog dvoje djece. Nastavite ovim putem u stazi dok se ne zadovolji svojstvo hrpe. Postupak može doći do lista.

Ojačavajući

Heapify znači sortiranje nerazvrstanog niza kako bi se svojstvo hrpe zadovoljilo za max-heap ili min-heap. To znači da u novom nizu mogu biti neka prazna mjesta. Osnovni algoritam za gomilanje max-heap ili min-heap je sljedeći:

- ako je korijenski čvor ekstremniji od bilo kojeg čvora njegova djeteta, tada zamijenite korijen s manje ekstremnim podređenim čvorom.

- Ponovite ovaj korak s podređenim čvorovima u shemi prelaska stabla predbilježbe.

Konačno stablo je stablo hrpe koje zadovoljava svojstvo hrpe. Hrpa se može predstaviti kao dijagram stabla ili u nizu. Rezultirajuća gomila djelomično je sortirano stablo, tj.e. djelomično razvrstani niz.

Pojedinosti o radu hrpe

Ovaj odjeljak članka daje pojedinosti o operacijama hrpe.

Stvaranje detalja hrpe

stvoriti_heap

Vidi gore!

otežati

Vidi gore

sjediniti

Ako niz hrpe,

89, 85, 87, 84, 82, 79, 73, 80, 81,,, 65, 69

i

89, 85, 84, 73, 79, 80, 83, 65, 68, 70, 71

su spojeni, rezultat bez duplikata može biti,

89, 85, 87, 84, 82, 83, 81, 80, 79, 73, 68, 65, 69, 70, 71

Nakon nekog prosijavanja. Primijetite da u prvom nizu 82 nema djece. U rezultirajućem nizu nalazi se na indeksu 4; a njegova mjesta s indeksom 2 (4) + 1 = 9 i 2 (4) + 2 = 10 su slobodna. To znači da u novom dijagramu stabla također nema djece. Izvorne dvije hrpe ne bi se trebale brisati jer njihovi podaci zapravo nisu u novoj hrpi (novi niz). Osnovni algoritam za spajanje hrpa istog tipa je sljedeći:

- Spojite jedan niz na dno drugog polja.

- Heapify uklanja duplikate, osiguravajući da čvorovi koji nisu imali djece u izvornim hrpama, još uvijek nemaju djece u novoj hrpi.

spojiti se

Algoritam za spajanje dvije gomile istog tipa (bilo dvije max- ili dvije min-) je sljedeći:

- Usporedite dva korijenska čvora.

- Napravite manje ekstremni korijen i ostatak njegovog stabla (podstablo), drugo dijete krajnjeg korijena.

- Prosijte zalutalo dijete korijena sada ekstremnog podstabla, prema dolje u krajnje podstablo.

Rezultirajuća hrpa i dalje je u skladu sa svojstvom hrpe, dok su izvorne hrpe uništene (izbrisane). Izvorne hrpe mogu se uništiti jer su svi podaci koje su posjedovali još uvijek u novoj hrpi.

Osnovne operacije hrpe

pronađi_max (pronađi_min)

To znači locirati maksimalnu vrijednost u polju max-heap i vratiti kopiju, ili minimalnu vrijednost u polje min-heap i vratiti kopiju. Niz hrpe po definiciji već zadovoljava svojstvo hrpe. Dakle, samo vratite kopiju prvog elementa niza.

umetnuti

To znači dodati novi element u niz hrpe i preurediti niz tako da se zadrži svojstvo hrpe dijagrama (zadovoljeno). Algoritam za to za obje vrste gomila je sljedeći:

- Pretpostavimo puno binarno stablo. To znači da se niz na kraju mora popuniti praznim mjestima, ako je potrebno. Ukupan broj čvorova pune hrpe je 1, ili 3 ili 7 ili 15 ili 31, itd.; nastavi udvostručavati i dodavati 1.

- Postavite čvor po veličini na najprikladnije prazno mjesto, prema kraju hrpe (prema kraju niza hrpe). Ako nema praznog mjesta, započnite novi redak dolje lijevo.

- Prosijte ako je potrebno, dok se ne zadovolji svojstvo hrpe.

ekstrakt_max (ekstrakt_min)

Pronađite maksimalnu vrijednost u polju max-heap, uklonite je i vratite; ili pronađite minimalnu vrijednost u polju min-heap, uklonite je i vratite. Algoritam za ekstrahiranje_maksa (ekstrakt_min) je sljedeći:

- Uklonite korijenski čvor.

- Uzmite (uklonite) krajnji desni čvor (posljednji čvor u nizu) i postavite ga u korijen.

- Prosijte prema potrebi, dok ne zadovolji svojstvo hrpe.

delete_max (delete_min)

Pronađite korijenski čvor max-heap, koji je prvi element polja max-heap, uklonite ga bez nužnog vraćanja; ili locirajte korijenski čvor min-heap, koji je prvi element polja min-heap, uklonite ga bez nužnog vraćanja. Algoritam za brisanje korijenskog čvora je sljedeći:

- Uklonite korijenski čvor.

- Uzmite (uklonite) krajnji desni čvor (posljednji čvor u nizu) i postavite ga u korijen.

- Prosijte prema potrebi, dok ne zadovolji svojstvo hrpe.

zamijeniti

Pronađite korijenski čvor bilo koje hrpe, uklonite ga i zamijenite novim. Nije važno hoće li se vratiti stari korijen. Prosijte prema potrebi, dok ne zadovolji svojstvo hrpe.

Interne operacije hrpe

tipka_većanja (tipka_manja)

Povećajte vrijednost bilo kojeg čvora za max hrpu i preuredite tako da se zadrži svojstvo hrpe ili smanjite vrijednost bilo kojeg čvora za min hrpu i preuredite tako da se zadržava svojstvo hrpe. Prosijte prema gore ili prema dolje, dok ne zadovolji svojstvo hrpe.

izbrisati

Uklonite čvor od interesa, a zatim ga preuredite tako da se zadržava svojstvo hrpe za max-heap ili min-heap. Algoritam za brisanje čvora je sljedeći:

- Uklonite čvor od interesa.

- Uzmi (ukloni) krajnji donji čvor (zadnji čvor u polju) i postavi na indeks uklonjenog čvora. Ako je čvor izbrisan u zadnjem redu, to možda neće biti potrebno.

- Prosijte prema gore ili prema dolje, dok ne zadovolji svojstvo hrpe.

shift_up

Pomaknite čvor prema gore u max-heap ili min-heap koliko god je potrebno, preslagivanjem kako biste održali svojstvo hrpe - prosijte.

pomaknuti dolje

Pomaknite čvor prema dolje u max-heap ili min-heap koliko god je potrebno, preslagivanjem kako biste održali svojstvo hrpe - prosijte dolje.

Pregled hrpe

veličina

Vidi gore!

prazno je

Vidi gore!

Ostale klase gomila

Hrpa opisana u ovom članku može se smatrati glavnom (generalnom) hrpom. Postoje i druge klase gomila. Međutim, dvoje koje biste trebali znati i dalje od ovoga su Binarna hrpa i d-arna hrpa.

Binarna hrpa

Binarna hrpa slična je ovoj glavnoj hrpi, ali s više ograničenja. Konkretno, binarna hrpa mora biti cjelovito stablo. Ne brkajte između cjelovitog i punog stabla.

d-arna hrpa

Binarna hrpa je 2-arna hrpa. Hrpa u kojoj svaki čvor ima po 3 djece trostruka je hrpa. Hrpa u kojoj svaki čvor ima po 4 djece je 4-arna hrpa i tako dalje. D-arina hrpa ima i druga ograničenja.

Zaključak

Hrpa je cjelovito ili gotovo potpuno binarno stablo koje zadovoljava svojstvo hrpe. Svojstvo hrpe ima dvije alternative: za max-heap roditelj mora biti jednak ili veći u vrijednosti od neposredne djece; za minimalnu hrpu, roditelj mora biti jednak ili manji u vrijednosti od neposredne djece. Hrpa se može predstaviti kao stablo ili u nizu. Kada je predstavljen u nizu, korijenski čvor je prvi čvor niza; i ako je čvor s indeksom n, njegovo je prvo dijete u nizu s indeksom 2n + 1, a njegovo sljedeće dijete s indeksom 2n + 2. Hrpa ima određene operacije koje se izvode na nizu.

Chrys