5270659532

Kopiec zupełny

Kopiec zupełny - to kopiec i zarazem zupełne drzewo binarne, czyli takie, w którym wszystkie poziomy są wypełnione całkowicie z wyjątkiem co najwyżej ostatniego, który jest spójnie wypełniony od strony lewej.

Ze względu na regularną strukturę kopca zupełnego, można go reprezentować w prosty sposób w tablicy. Następniki węzła k (o ile istnieją) mają odpowiednio numery 2k i 2k+l, zaś poprzednik węzła k (różny od korzenia) ma numer |_k/2_|:

2° węzłów

2¹ węzłów

2² węzłów 1) węzłów

PODSTAWY INFORMATYKI. Adrian Horzyk, http://home.agh.edu.pl/--horzyk    Wykład 6. Strona 16.