Redovi sa prioritetom se obično implementiraju korišćenjem strukture podataka hip. Za razliku od binarnog hipa u kom operacije umetanja elementa ima logaritamsku složenost, Fibonačijev hip je struktura podataka kod koje operacije umetanja novog elementa u strukturu ima konstantnu amortizovanu složenost, što je čini bržom. Dodatno, Fibonačijev hip omogućava i spajanje dva hipa u jedan kao i smanjivanje vrednosti ključa u konstantnoj amortizovanoj složenosti, dok složenost izbacivanja minimuma ostaje logaritamska. Dakle, Fibonačijev hip uspešno rešava sledeći problem.
Problem. Definisati strukturu podataka koja podržava efikasno izvršavanje (u amortizovanom konstantnom ili logaritamskom vremenu) sledećih operacija:
napravi_hip() - pravi novi prazni hipumetni(H, v) - umeće element sa vrednošću ključa v u hip Hminimum(H) - vraća element hipa H sa minimalnom vrednošću ključaizbaci_minimum(H) - briše element hipa H sa minimalnom vrednošću ključa i vraća ga kao rezultatunija(H1,H2) - od dva hipa H1 i H2 pravi novi hip koji sadrži sve elemente polaznih hipovasmanji_kljuc(H, x, v) - elementu x hipa H menja vrednost ključa novom vrednošću v, pri čemu je v manja ili jednaka od trenutne vrednosti ključa elementa xImplementacija operacije smanji_kljuc zahteva pamćenje dodatnih podataka u strukturi, pa je implementacija hipa koji podržava tu operaciju malo komplikovanija nego implementacija hipa koji podržava sve ostale navedene operacije.
Amortizovana složenost operacija pravljenja hipa, umetanja elementa, određivanja minimuma, pravljenja unije i smanjivanja vrednosti ključa je \(O(1)\), dok je amortizovana složenost operacije brisanja minimalnog elementa iz hipa \(O(\log n)\). Dakle, operacije umetanja elementa i pravljenja unije se efikasnije izvršavaju nad Fibonačijevim hipom, nego nad klasičnim binarnim hipom (podsetimo se, složenost dodavanja elemenata u binarni hip je \(O(\log{n})\)).
Fibonačijev hip je koristan kada je broj operacija brisanja minimalnog elementa iz hipa mali u odnosu na ostale pomenute operacije. Na primer, u grafovskim algoritmima kao što je određivanje razapinjućeg (povezujućeg) drveta minimalne cene ili najkraćih puteva iz zadatog čvora, ako je graf gust (sadrži veliki broj grana), operacija smanjivanja vrednosti ključa se može često javljati, te ubrzanje sa \(O(\log n)\) kod binarnog hipa na \(O(1)\) kod Fibonačijevog hipa može doneti osetno ubrzanje. Nedostatak Fibonačijevog hipa je to što je dosta teži za implementaciju od klasičnog, binarnog hipa, to što zahteva više memorije, kao i to što je složenost najgoreg slučaja nekih operacija velika.
Fibonačijev hip je dobio naziv prema Fibonačijevim brojevima na osnovu kojih se formuliše centralna invarijanta koja garantuje dobru složenost operacija. Ovu strukturu podataka osmislili su Fridman i Tardžan sa ciljem da se poboljša vreme izvršavanja Dajkstrinog algoritma za određivanje najkraćih puteva iz zadatog čvora. Međutim, ona ima primene i u drugim grafovskim algoritmima, poput Primovog algoritma za računanje minimalnog povezujućeg drveta, za određivanje maksimalnog toka kroz mrežu, ali i u drugim domenima, poput geometrijskih algoritama, obrade slika i matematičke optimizacije.
Fibonačijev min-hip predstavlja kolekciju min-hipova. Svaki mih-hip je drvo u kom čvorovi mogu imati različit broj naslednika, a vrednost u svakom čvoru je manja ili jednaka vrednosti u njegovim naslednicima. Redosled drveta u Fibonačijevom hipu je proizvoljan. Fibonačijevom hipu pristupamo putem pokazivača na koren drveta sa minimalnom vrednošću u celom Fibonačijevom hipu – ovaj čvor zovemo minimalnim čvorom Fibonačijevog hipa (ukoliko postoji više čvorova sa minimalnom vrednošću bilo koji od njih se može proglasiti minimalnim čvorom). Jedan primer Fibonačijevog min-hipa prikazan je na slici 2. Koreni svih drveta u Fibonačijevom hipu se povezuju u kružnu, dvostruko povezanu listu koju nazivamo lista korenova hipa. I sva deca bilo kog čvora su međusobno povezana u kružnu, dvostruko povezanu listu. Svaki čvor (bilo da je koren ili ne) sadrži pokazivač na levog i desnog suseda i na neko dete (a ako je potrebno vršiti i operacije smanjivanja vrednosti ključeva, onda i pokazivač na roditelja i još neke pomoćne podatke koje ćemo opisati u sklopu opisa te operacije). Korišenje kružnih lista omogućava umetanje novih čvorova u te liste i brisanje čvorova iz lista u vremenu \(O(1)\). Takođe, dve ovakve liste možemo objediniti u novu listu takođe u vremenu \(O(1)\) (videćemo da je ovo bitno za efikasno izvođenje operacije formiranja unije). Ove operacije nad listama su gradivni elementi operacija nad hipom i njihova efikasnost garantuje efikasno izvršavanje operacija nad hipom.
Broj dece čvora naziva se stepen čvora. Navedimo sada ključnu invarijantu (uslov koji važi nakon formiranja strukture i nakon primene bilo koje operacije za koji ćemo videti da garantuje složenost operacija).
Invarijanta (broj čvorova poddrveta): Svako poddrvo Fibonačijevog hipa čiji je koren stepena \(d\) sadrži bar \(F_{d+2}\) čvorova, gde je sa \(F_k\) označen \(k\)-ti Fibonačijev broj (\(F_0=0\), \(F_1=1\), \(F_{k} = F_{k-1} + F_{k-2}\)).
Dakle, drvo čiji je koren stepena 0 ima bar 1 čvor, stepena 1 ima bar 2 čvora, stepena 2 ima bar 3 čvora, stepena 3 ima bar 5 čvorova, stepena 4 ima bar 8 čvorova itd.). Pošto se lako (indukcijom) dokazuje da je \(F_{d+2} \geq \varphi^d\), gde je \(\varphi=\frac{1 + \sqrt{5}}{2}\), za stepen \(d\) svakog čvora koji je koren nekog poddrveta u kom se nalazi \(m\) čvorova važi \(m \geq F_{d+2} \geq \varphi^d\) tj. \(d \leq \log_\varphi{m}\). Dakle, broj dece svakog čvora koji je koren poddrveta sa \(m\) elemenata je \(O(\log{m})\). Ako u celom Fibonačijevom hipu ima \(n\) elemenata, stepen bilo kog čvora je \(O(\log{n})\). Dakle, pod uslovom da invarijanta važi, liste dece su relativno kratke i prolazak kroz sve elemente takve liste vrši se u logaritamskoj složenosti (u odnosu na ukupan broj elemenata u hipu).
Formulišimo sada drugačiju invarijantu, koju je lakše proveravati, a koja daje garancije da će važiti invarijanta o broju čvorova u poddrvetima.
Invarijanta (stepeni dece): Za svaki čvor \(x\) stepena \(d\) važi da su stepeni dece bar \(0, 0, 1, 2, \ldots, d-2\).
Indukcijom se dokazuje da invarijanta o stepenima dece garantuje invarijantu o broju čvorova poddrveta. Ako je \(d=0\), čvor nema dece, a u njegovom poddrvetu se nalazi \(F_2=1\) čvor. Ako je invarijanta o stepenima dece ispunjena, na osnovu induktivne hipoteze važi da poddrveta čiji su koreni deca čvora \(x\) sadrže redom \(F_2, F_2, F_3, \ldots F_d\) čvorova, pa, pošto je \(F_2=F_1=1\) i \(F_0=0\), važi da je ukupan broj čvorova u drvetu čiji je koren \(x\) jednak \(1 + F_0 + F_1 + F_2 + F_3 \ldots + F_d\) (prva jedinica dolazi od samog korena \(x\)). Indukcijom se rutinski može dokazati da je \(1 + F_0 + F_1 + F_2 + \ldots + F_d = F_{d+2}\), pa invarijanta o stepenima dece zaista implicira invarijantu o broju čvorova poddrveta.
Ova invarijanta nameće određene stepene dece, ali nije precizirano koja deca treba da imaju tražene stepene. Deca se razmatraju u redosledu njihovog dodavanja roditeljskom čvoru i njihovi stepeni u tom redosledu zadovoljavaju invarijantu (a ne po redosledu kojim su smešteni u listu dece). Dakle, uslov koji je dovoljan da bi hip bio Fibonačijev je da su stepeni dece u redosledu dodavanja \(0, 0, 1, 2, 3, \ldots\) tj. da za svaki čvor važi da njegovo dete sa rednim brojem dodavanja \(i\) (brojimo od nule) ima stepen \(d_i \geq i-1\) (pri čemu je i \(d_i \geq 0\), jer je \(d_i\) prirodan broj).
Videćemo uskoro da će procedura formiranja hipa biti takva da su stepeni dece svakog čvora drveta neposredno nakon njegovog prvog formiranja biti \(0, 1, 2, 3, \ldots\) (što je i više nego što se zahteva invarijantom o stepenima dece). Na osnovu ovoga se može dokazati da svako poddrvo čiji je stepen korena \(d\) ima \(2^d\) čvorova, što takođe garantuje povoljnu složenost operacija. Ipak, invarijanta je oslabljena da bi bilo moguće uklanjati čvorove iz formiranog drveta, što je, videćemo, veoma važno za realizaciju operacije smanjivanja vrednosti ključa (engl. smanji_kljuc).
Na slici 1 levo vidi se najgušće moguće popunjeno drvo (koje se dobija odmah nakon formiranja drveta koje sadrži \(2^5=32\) čvora), dok se desno vidi najređe moguće drvo koje zadovoljava invarijantu i koje sadrži \(F_{5+2} = 13\) čvorova. Izbacivanjem bilo kog čvora iz desnog drveta bila bi narušena invarijanta.
Prikažimo, napokon, jedan kompletan primer Fibonačijevog hipa.
Primer 1.2.1. Na slici 2 prikazan je Fibonačijev hip koji se sastoji od \(6\) min-hipova. Minimalni element u hipu je minimum svih korenova, a to je element sa ključem \(4\).
Direktnom proverom se lako može pokazati invarijanta o stepenima dece. Ona je uvek trivijalno ispunjena za čvorove čiji je stepen \(0\), \(1\) i \(2\) (jer su stepeni dece uvek veći ili jednaki od 0 što se invarijantom traži). Deca čvora \(47\) imaju redom stepene \(0\), \(0\) i \(1\), a deca čvora \(4\) imaju redom redom stepene \(0\), \(1\) i \(2\). Dakle, za svaki čvor jeste zadovoljena invarijanta o stepenima dece (stepeni dece su na nekim mestima veći nego što je potrebno), a ona garantuje i invarijantu o veličinama tj. ukupnom broju čvorova tih drveta. Zaista, drveta koja čine Fibonačijev hip redom imaju \(1\), \(2\), \(6\), \(1\), \(8\), \(1\) i \(1\) čvor, što je ponekad i više od odgovarajućih Fibonačijevih brojeva \(1\), \(2\), \(5\), \(1\), \(5\), \(1\) i \(1\). Isto važi i za sva njihova poddrveta, pa je centralna invarijanta o veličinama svih drveta zadovoljena.
Jedna od osnovnih karakteristika operacija nad Fibonačijevim hipom je lenjo izvršavanje operacija, tj. posao se odlaže za što je moguće kasnije.
Umetanje novog elementa u Fibonačijev hip (operacija insert(H, x)) se vrši tako što se novi element dodaje u listu korenova, ažurirajući minimalni čvor, ako je potrebno, što je konstantne vremenske složenosti. Dakle, umetanjem \(k\) elemenata u prazan Fibonačijev hip dobija se Fibonačijev hip čija lista korenova ima \(k\) elemenata.
Primer 1.2.2. Umetanjem elementa sa ključem \(30\) u prethodni Fibonačijev hip dobija se hip prikazan na slici 3 (novi element je dodat na kraj liste korenova, ali mogao je biti dodat i na bilo koje drugo mesto, najčešće je to neposredno iza ili ispred minimalnog čvora, na koji, podsetimo se, ukazuje poseban pokazivač).
Unija dva Fibonačijeva hipa \(H_1\) i \(H_2\) (operacija unija(H1, H2)) se pravi nadovezivanjem listi korenova ova dva hipa i određivanjem novog minimalnog čvora (to je manji od dva minimalna čvora polaznih hipova). Ovo je takođe operacija konstantne složenosti.
Određivanje minimalnog elementa u Fibonačijevom hipu (operacija minimum(H)) je trivijalno, s obzirom na to da se u svakom trenutku čuva pokazivač na minimalni element u strukturi. Ovo je takođe operacija konstantne složenosti.
Operacija brisanja najmanjeg elementa iz Fibonačijevog hipa (operacija izbaci_minimum(H)) se izvodi na sledeći način: prvo se sva njegova deca umeću u listu korenova, i on se briše iz liste korenova. Da bi se ažurirao minimum hipa potrebno je potencijalno proći kroz celu listu korenova, koja može biti veoma duga. Zbog toga se pre ažuriranja minimuma vrši jedna posebna pomoćna operacija koja se naziva konsolidacija hipa, odnosno hip se dovodi u stanje u kom svi korenovi imaju različit stepen, što dovodi do toga da se njihov broj značajno smanjuje (na osnovu ranije pokazane veze između stepena korenova i veličine drveta, jasno je da su svi stepeni korenova \(O(\log{n})\), pa ih ne može biti više od \(O(\log{n})\)).
Konsolidacija se vrši na sledeći način: sve dok neka dva čvora iz liste korenova imaju isti stepen vrši se spajanje korenova istog stepena tj. radi se sledeće:
pronalaze se dva čvora \(x\) i \(y\) u listi korenova koja su istog stepena (bez smanjenja opštosti neka važi da je vrednost ključa čvora \(x\) manja ili jednaka od vrednosti ključa čvora \(y\))
\(y\) se izbacuje iz liste korenova i proglašava se detetom čvora \(x\). Na ovaj način, drvo sa korenom \(x\) ostaje hip i stepen čvora \(x\) se povećava za jedan. Na osnovu invarijante o stepenima dece znamo da važi da je poslednje dodati naslednik čvora \(x\) imao bar stepen \(d-2\), gde je \(d\) stepen čvora \(x\). To znači da bi naredni tj. poslednji dodati naslednik, što je upravo \(y\), morao da ima stepen bar \(d-1\). Međutim, mi znamo da on ima stepen \(d\) (jer mu je stepen jednak stepenu čvora \(x\)), tako da je invarijanta zadovoljena, uz jedan dodatni stepen slobode. Naime, čak i kada uklonimo jednog naslednika čvora \(y\), invarijanta ostaje zadovoljena. Sa druge strane, uklanjanje dva naslednika bi narušilo invarijantu i to ne smemo da radimo. Ovo je značajno za operaciju smanjivanja vrednosti elemenata hipa smanji_kljuc i vratićemo se na ovo prilikom opisa te operacije.
Naglasimo da je izbor para čvorova sa istim stepenima u svakom koraku proizvoljan (konsolidacija se ne mora se vršiti ni u kakvom posebnom redosledu parova čvorova).
Obično se za realizovanje konsolidacije koristi pomoćni niz u koji se smeštaju pokazivači na čvorove iz liste korenova, tako da se na poziciji \(i\) čuva pokazivač na neki čvor iz liste korenova koji je stepena \(i\). Dimenzija ovog pomoćnog niza jednaka je maksimalnom stepenu \(D(n)\) proizvoljnog čvora u Fibonačijevom hipu – već smo objasnili da je on jednak \(O(\log n)\), gde je sa \(n\) označen broj elemenata hipa. Korenovi koji su istog stepena se detektuju na sledeći način: prolazi se redom kroz listu korenova i ukoliko je tekući koren stepena \(i\), a \(i\)-ti element niza je još uvek prazan, on se inicijalizuje pokazivačem na dati koren, a ukoliko je \(i\)-ti element već postavljen, pronađena su dva korena istog stepena i oni se spajaju.
Primer 1.2.3. Pogledajmo kako se menja prethodni hip nakon izvođenja operacije brisanja elementa sa minimalnom vrednošću ključa.
U prvom koraku se sva deca uklonjenog minimalnog čvora \(4\) umeću u niz korenova.
Nakon toga izvršavamo konsolidaciju, tj. spajanje drveta čiji su koreni istog stepena.
Analizirajmo složenost prethodno opisanog postupka. Deca se efikasno, algoritmom složenosti \(O(1)\) mogu umetnuti u listu korenova (radi se o spajanju dve liste). Nakon toga se vrši konsolidacija, koja u najgorem slučaju može biti i linearne složenosti (najgori slučaj je kada se \(n\) jednočlanih drveta spaja). Ipak, može se pokazati da je amortizovana složenost konsolidacije \(O(\log{n})\) – neformalno, kada se jednom izvrši konsolidacija i dobije se mali broj velikih drveta, svaki naredni korak izbacivanja najmanjeg elementa i konsolidacije biće prilično efikasan. Na kraju se pronalazi novi minimalni čvor, obradom svih korenova. Njih nakon konsolidacije može biti najviše \(O(\log{n})\), pa je ovo efikasna operacija.
Prikažimo sada jednu jednostavnu implementaciju ovih operacija (jednostavnosti radi, koristimo globalne promenljive i ne vodimo računa o alokaciji i dealokaciji memorije).
// Cvor drveta sadrzi podatak i dvostruko povezanu listu dece
struct Cvor {
int podatak;
list<Cvor*> deca;
};
// dvostruko povezana lista korenova
list<Cvor*> hip;
// pokazivac (iterator) koji ukazuje na najmanji cvor
list<Cvor*>::iterator minCvor;
// umetanje novog elementa u hip
void umetni(int podatak) {
// pravimo novi cvor i upisujemo podatak u njega
Cvor* novi = new Cvor();
novi->podatak = podatak;
if (hip.empty()) {
// ako je hip prazan ubacujemo novi cvor u njega i taj novi cvor je minimalan
hip.push_back(novi);
minCvor = hip.begin();
} else {
// ako hip nije prazana ubacujemo novi cvor u njega
hip.push_front(novi);
// minimum azuriramo samo ako je novi podatak manji od dotadasnjeg minimalnog
if (novi->podatak < (*minCvor)->podatak)
minCvor = hip.begin();
}
}
// najmanji element hipu
int minimum() {
return (*minCvor)->podatak;
}
// konsolidacija hipa (pomocna operacija kojom se skracuje lista korenova)
void konsoliduj() {
// za svaki moguci broj dece pamtimo jedan koren koji ima toliko
// dece u njemu ce se nalaziti svi koreni novog hipa (i svi koreni
// ce imati razlicit broj dece)
const int MAKS_DECE = 64;
Cvor* pom[MAKS_DECE] = {};
// obradjujemo jedan po jedan koren hipa
for (Cvor* x : hip) {
// dok postoji drugi koren (u novom hipu) sa istim brojem dece kao x
int brojDece = x->deca.size();
while (pom[brojDece] != nullptr) {
// spajamo dva korena tako da je manji podatak iznad
Cvor* y = pom[brojDece];
if (x->podatak > y->podatak)
swap(x, y);
x->deca.push_back(y);
// kada mu se pridruzi y, koren x ima jedno dete vise, a u novom hipu vise
// ne postoji hip koji ima stari broj dece
pom[brojDece] = nullptr;
brojDece++;
}
// upisujemo x u novi hip
pom[brojDece] = x;
}
// prebacujemo sve korene iz novog hipa u stari
hip.clear();
for (Cvor* cvor : pom)
if (cvor != nullptr)
hip.push_back(cvor);
}#include <iostream>
#include <list>
using namespace std;
// Cvor drveta sadrzi podatak i dvostruko povezanu listu dece
struct Cvor {
int podatak;
list<Cvor*> deca;
};
// dvostruko povezana lista korenova
list<Cvor*> hip;
// pokazivac (iterator) koji ukazuje na najmanji cvor
list<Cvor*>::iterator minCvor;
// umetanje novog elementa u hip
void umetni(int podatak) {
// pravimo novi cvor i upisujemo podatak u njega
Cvor* novi = new Cvor();
novi->podatak = podatak;
if (hip.empty()) {
// ako je hip prazan ubacujemo novi cvor u njega i taj novi cvor je minimalan
hip.push_back(novi);
minCvor = hip.begin();
} else {
// ako hip nije prazana ubacujemo novi cvor u njega
hip.push_front(novi);
// minimum azuriramo samo ako je novi podatak manji od dotadasnjeg minimalnog
if (novi->podatak < (*minCvor)->podatak)
minCvor = hip.begin();
}
}
// najmanji element hipu
int minimum() {
return (*minCvor)->podatak;
}
// konsolidacija hipa (pomocna operacija kojom se skracuje lista korenova)
void konsoliduj() {
// za svaki moguci broj dece pamtimo jedan koren koji ima toliko
// dece u njemu ce se nalaziti svi koreni novog hipa (i svi koreni
// ce imati razlicit broj dece)
const int MAKS_DECE = 64;
Cvor* pom[MAKS_DECE] = {};
// obradjujemo jedan po jedan koren hipa
for (Cvor* x : hip) {
// dok postoji drugi koren (u novom hipu) sa istim brojem dece kao x
int brojDece = x->deca.size();
while (pom[brojDece] != nullptr) {
// spajamo dva korena tako da je manji podatak iznad
Cvor* y = pom[brojDece];
if (x->podatak > y->podatak)
swap(x, y);
x->deca.push_back(y);
// kada mu se pridruzi y, koren x ima jedno dete vise, a u novom hipu vise
// ne postoji hip koji ima stari broj dece
pom[brojDece] = nullptr;
brojDece++;
}
// upisujemo x u novi hip
pom[brojDece] = x;
}
// prebacujemo sve korene iz novog hipa u stari
hip.clear();
for (Cvor* cvor : pom)
if (cvor != nullptr)
hip.push_back(cvor);
}
void ispisiDrvo(Cvor* cvor);
void ispisi(const list<Cvor*>& lista) {
for (Cvor* cvor : lista)
ispisiDrvo(cvor);
}
void ispisiDrvo(Cvor* cvor) {
if (cvor != nullptr) {
cout << cvor->podatak;
cout << "[";
ispisi(cvor->deca);
cout << "]";
}
}
void izbaciMinimum() {
hip.splice(hip.end(), (*minCvor)->deca);
delete *minCvor;
hip.erase(minCvor);
konsoliduj();
minCvor = hip.begin();
for (auto it = hip.begin(); it != hip.end(); it++)
if ((*it)->podatak < (*minCvor)->podatak)
minCvor = it;
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
umetni(x);
}
while (hip.size() > 0) {
cout << minimum() << " ";
izbaciMinimum();
}
return 0;
}Još jedna važna operacija nad Fibonačijevim hipom jeste smanjivanje vrednosti ključa čvoru \(x\) (operacija smanji_kljuc(H, x, v)). Pretpostavljamo da je čvor \(x\) kome se vrednost umanjuje već poznat tj. da je poznat pokazivač na njega (jer je to slučaj u mnogim algoritmima koji koriste Fibonačijeve hipove). Ako nije, tj. ako pretpostavljamo da je poznata samo vrednost ključa koja se umanjuje, ali ne i čvor koji sadrži tu vrednost (to je operacija smanji_vrednost(H, k, v)) onda se čvor \(k\) sa vrednošću ključa \(k\) može efikasno pronaći tako što se čuva mapa koja slika ključeve u pokazivače na čvorove (dovoljno je da se vrednost ključa slika u pokazivač na bilo koji čvor koji je sadrži).
Da bi se ova operacija mogla efikasno implementirati, potrebno je čvorove proširiti sa nekoliko dodatnih podataka, koje ćemo u tekstu opisati.
Smanjivanje vrednosti ključa se izvodi na sledeći način: prvo se datom čvoru \(x\) promeni vrednost ključa na \(v\), a zatim se, ako \(x\) nije koren, ta vrednost poredi sa vrednošću ključa roditelja. Kako bi se moglo pristupiti roditelju, u svim čvorovima se čuva informacija o roditeljskom čvoru (ona ne mora biti definisana jedino u korenima drveta). Ako je \(x\) koren ili je vrednost ključa roditelja čvora \(x\) manja ili jednaka \(v\), onda uslov hipa nije narušen te nisu potrebne nikakve dalje izmene. Ako to nije slučaj, uslov hipa je narušen te je hip potrebno preurediti. Najpre se vrši odsecanje grane između čvora \(x\) i njegovog roditelja i poddrvo sa korenom \(x\) se dodaje u listu korenova.
Postavlja se pitanje da li je drvo iz kojeg je isečen čvor \(x\) potrebno dalje preuređivati. Odgovor zavisi od toga da li je izbacivanjem poddrveta sa korenom \(x\) narušena invarijanta o broju čvorova u tom drvetu, tj. da li je narušena invarijanta o stepenima dece. Podsetimo se da su nakon konsolidacije čvorovi u drvetu obično takvi da imaju jedno dete više od onoga što bi trebalo da imaju na osnovu invarijante tj. da im je moguće ukloniti jedno dete (tj. poddrvo kojem je ono koren), a da invarijanta za njegovog roditelja i dalje bude zadovoljena. Sa druge strane, uklanjanje dva deteta narušava invarijantu. Dakle, postavlja se pitanje da li smo roditelju čvora \(x\) već uklonili neko dete od trenutka kada je ubačen u trenutno drvo. Da bismo to znali, svaki čvor pored informacije o svom stepenu (broju svoje dece), sadrži i oznaku da li je ,,izgubio’’ dete od poslednjeg trenutka kada je postao dete nekog drugog čvora. Čvorovi se inicijalno ne označavaju i svaki put kada čvor postane dete nekog drugog čvora ili koren, ukoliko je bio označen, oznaka se uklanja. Ako jedan čvor izgubi dva deteta, odsecamo i roditelja i postupak se nastavlja po istom principu, naviše, uz drvo. Preciznije, vrši se sledeći niz koraka:
Primer 1.2.4. Razmotrimo hip prikazan na slici 4. Gore-desno od svakog čvora napisan je trenutni stepen čvora i minimalni stepen koji čvor mora imati na osnovu invarijante. Na početku skoro svi čvorovi imaju i veći stepen nego što je to potrebno.
Naredni aplet Vam omogućava da sagledate operacije.
✖