Elementarne struktury danych: drzewo binarne kolejka priorytetowa
Oglnie rzecz biorc drzewo binarne to takie w ktrym kady element poza korzeniem ma ojca, oraz dwch, jednego, bd zero synw w takim przypadku element nazywany jest liciem. Pene drzewo binarne to takie, w ktrym tylko najniszy poziom moe by niepeny, lecz owa niepeno musi by, e tak powiem, uporzdkowana. To znaczy jakby rozrysowa sobie takie drzewko, to jeeli wystpuje spjny cig elementw od lewej strony na najniszym poziomie i aden inny element na tym poziomie si nie znajduje to drzewo binarne jest pene.
Pene drzewo binarne jest wyjtkowo mi struktur, bowiem mona umieci j w tablicy bez adnych wskanikw do synw i ojcw, poniewa mona sobie offsety do nich policzy. I tak zakadajc e korze jest elementem zerowym tablicy m0 to majc element zajmujcy pozycj x w tablicy mx moemy znale jego ojca mx-1/2 jego lewego syna mx*2+1 i prawego mx*2+2.
Z takim penym drzewem binarnym moemy zrobi wiele ciekawych rzeczy. Moemy zrobi sobie z tego na przykad kolejk priorytetow, albo napisa oparte na nim sortowanie dziaajce niby w Onlogn, ale i tak quicksort okazuje si zazwyczaj szybszy. Kolejka priorytetowa jest do przydatn struktur, poniewa pozwala znale najwikszy element bd najmniejszy, zaley jak sobie j napiszemy, niestety nie jest moliwe szukanie min max w jednej kolejce w czasie O1, mona te znale i usun najwikszy element w czasie Ologn i w takim samym czasie doda nowy element. Czas logn dla 65536 wynosi po prostu 16, wic sami widzicie, e jest to szybka i efektowna struktura. A oto przykadowa implementacja akurat do wyszukiwania minimum:
class heap
public:
long n, m10000
void insert long x
mn x
if n0 pushup n
n++
long delmin void
long tmp m0
m0 m--n
pushdown 0
return tmp
long min void
return m0
void pushup long x
while mxmx-1/2
long tmp mx
mx mx-1/2
mx-1/2 tmp
if x0 x x-1/2
void pushdown long x
while 1
long lx*2+1
long rx*2+2
long min x
if lnmlmmin
min l
if rnmrmmin
min r
if min!x
long tmp mmin
mmin mx
mx tmp
x min
else break
h
Jak wida powysza implementacja jest iteracyjna, nie rekurencyjna. Mimo e wersja rekurencyjna jest duo, duo prostsza do napisania, a i raczej trudno przepeni ni stos w kocu maksymalne zagbienie si procedury dla n elementw wynosi lgn, to mimo to czsto lepiej stosowa wanie wersj iteracyjn. Powody? Jest szybsza. Mimo i rnice midzy jedn a drug wersj s minimalne, to przy wykonywaniu kilku milionw wywoa zdejmowania/dodawania do stosu, rnica jest zauwaalna tzn. wersja iteracyjna dziaa o par/parnacie setnych sekund szybciej, co moe mie znaczenie. Najwaniejsze s tu dwie procedury - pushdown i pushup, ktre su do manipulowania elementami tak, eby zachowa waciwo stosu tzn. w tym przypadku aden z synw nie moe by mniejszy od ojca. Czsto koduje si je po prostu jako integralna cz procedur insert i delmin, jednak napisanie ich osobno pozwala na przywracanie waciwoci stosu w momencie zmiany klucza dla dowolnego elementu stosu. Dziaanie procedury pushdown jest nastpujce: sprawdzamy ktry z trzech elementw - ojca i jego dwch synw - jest najmniejszy. Jeeli jest to ojciec, to waciwoci stosu s zachowane wic przerywamy dziaanie. W Przypadku, w ktrym jest to ktry z synw zamieniamy go z ojcem i ca procedur powtarzamy tym razem dla niego. Dziaanie pushup polega na sprawdzaniu, czy dany element jest mniejszy od ojca. Jeli tak, to zamieniamy go z nim i powtarzamy czynnoci dla ojca. Easy?:
nostre/marsmellow
Oglnie rzecz biorc drzewo binarne to takie w ktrym kady element poza korzeniem ma ojca, oraz dwch, jednego, bd zero synw w takim przypadku element nazywany jest liciem. Pene drzewo binarne to takie, w ktrym tylko najniszy poziom moe by niepeny, lecz owa niepeno musi by, e tak powiem, uporzdkowana. To znaczy jakby rozrysowa sobie takie drzewko, to jeeli wystpuje spjny cig elementw od lewej strony na najniszym poziomie i aden inny element na tym poziomie si nie znajduje to drzewo binarne jest pene.
Pene drzewo binarne jest wyjtkowo mi struktur, bowiem mona umieci j w tablicy bez adnych wskanikw do synw i ojcw, poniewa mona sobie offsety do nich policzy. I tak zakadajc e korze jest elementem zerowym tablicy m0 to majc element zajmujcy pozycj x w tablicy mx moemy znale jego ojca mx-1/2 jego lewego syna mx*2+1 i prawego mx*2+2.
Z takim penym drzewem binarnym moemy zrobi wiele ciekawych rzeczy. Moemy zrobi sobie z tego na przykad kolejk priorytetow, albo napisa oparte na nim sortowanie dziaajce niby w Onlogn, ale i tak quicksort okazuje si zazwyczaj szybszy. Kolejka priorytetowa jest do przydatn struktur, poniewa pozwala znale najwikszy element bd najmniejszy, zaley jak sobie j napiszemy, niestety nie jest moliwe szukanie min max w jednej kolejce w czasie O1, mona te znale i usun najwikszy element w czasie Ologn i w takim samym czasie doda nowy element. Czas logn dla 65536 wynosi po prostu 16, wic sami widzicie, e jest to szybka i efektowna struktura. A oto przykadowa implementacja akurat do wyszukiwania minimum:
class heap
public:
long n, m10000
void insert long x
mn x
if n0 pushup n
n++
long delmin void
long tmp m0
m0 m--n
pushdown 0
return tmp
long min void
return m0
void pushup long x
while mxmx-1/2
long tmp mx
mx mx-1/2
mx-1/2 tmp
if x0 x x-1/2
void pushdown long x
while 1
long lx*2+1
long rx*2+2
long min x
if lnmlmmin
min l
if rnmrmmin
min r
if min!x
long tmp mmin
mmin mx
mx tmp
x min
else break
h
Jak wida powysza implementacja jest iteracyjna, nie rekurencyjna. Mimo e wersja rekurencyjna jest duo, duo prostsza do napisania, a i raczej trudno przepeni ni stos w kocu maksymalne zagbienie si procedury dla n elementw wynosi lgn, to mimo to czsto lepiej stosowa wanie wersj iteracyjn. Powody? Jest szybsza. Mimo i rnice midzy jedn a drug wersj s minimalne, to przy wykonywaniu kilku milionw wywoa zdejmowania/dodawania do stosu, rnica jest zauwaalna tzn. wersja iteracyjna dziaa o par/parnacie setnych sekund szybciej, co moe mie znaczenie. Najwaniejsze s tu dwie procedury - pushdown i pushup, ktre su do manipulowania elementami tak, eby zachowa waciwo stosu tzn. w tym przypadku aden z synw nie moe by mniejszy od ojca. Czsto koduje si je po prostu jako integralna cz procedur insert i delmin, jednak napisanie ich osobno pozwala na przywracanie waciwoci stosu w momencie zmiany klucza dla dowolnego elementu stosu. Dziaanie procedury pushdown jest nastpujce: sprawdzamy ktry z trzech elementw - ojca i jego dwch synw - jest najmniejszy. Jeeli jest to ojciec, to waciwoci stosu s zachowane wic przerywamy dziaanie. W Przypadku, w ktrym jest to ktry z synw zamieniamy go z ojcem i ca procedur powtarzamy tym razem dla niego. Dziaanie pushup polega na sprawdzaniu, czy dany element jest mniejszy od ojca. Jeli tak, to zamieniamy go z nim i powtarzamy czynnoci dla ojca. Easy?:
nostre/marsmellow
log in to add a comment.