Struktura kopca jest przykładem etykietowanego drzewa binarnego, wyważonego. Nie jest to jednak drzewo binarnych poszukiwań. Zasady etykietowania wierzchołków są inne, chociaż tak jak w przypadku drzew binarnych poszukiwań, zakłada się, że zbiór etykiet jest liniowo uporządkowany. Co więcej, kopiec, jako drzewo doskonałe, ma wszystkie ścieżki prawie tej samej długości. Zestaw dostępnych operacji w kopcu też jest inny niż w drzewach binarnych poszukiwań. Kopce stanowią strukturę danych, w której zwykle wykonujemy operacje wstawiania, znajdowana i usuwania minimum. Są to operacje charakterystyczne dla struktur zwanych kolejkami priorytetowymi. Będzie o tym mowa w następnym wykładzie. Ten punkt wykładu poświęcimy definicji kopca.

Definicja 1.1 Powiemy, że drzewo binarne jest doskonałe wtedy i tylko wtedy, gdy wszystkie poziomy drzewa są maksymalne zapełnione z wyjątkiem być może ostatniego poziomu, na którym wszystkie liście są zgrupowane maksymalnie na lewo.

Na mocy definicji 1.1, jeśli z drzewa doskonałego o wysokości h, usuniemy wszystkie liście z ostatniego poziomu, to otrzymamy pełne drzewo binarne o wysokości h-1 (por. rysunek 9.1 (a)). Charakterystyczny kształt drzewa doskonałego przedstawiono na rysunku 9.1 (b). Zaznaczone wierzchołki pełnią specjalną rolę przy wykonywaniu operacji na drzewie doskonałym.

Drzewo doskonałe o wysokości h, ma więc co najwyżej 2^h+1 -1 i co najmniej 2^h wierzchołków.

Lemat 1.1 Dla dowolnego drzewa doskonałego o n wierzchołkach i wysokości h zachodzą nierówności :

2^h -1 < n £ 2^h+1-1 .

lg(n+1)-1 £ h < lg(n+1)

W konsekwencji, wysokość h drzewa doskonałego o n wierzchołkach wynosi h = ëlg(n+1)û.

Definicja 1.2 Powiemy, że etykietowane drzewo binarne D = <V, E, et> jest częściowo uporządkowane wtedy i tylko wtedy, gdy dla dowolnego v ÎV, etykieta wierzchołka v jest mniejsza niż etykiety obu jego synów,

("vÎV) et(v) < et(v.left) Ù et(v) < et(v.right).

Z przyjętej definicji 1.2 wynika natychmiast, że w dowolnym drzewie częściowo uporządkowanym:

Definicja 1.3 Kopcem nazywamy etykietowane drzewo binarne, doskonałe, częściowo uporządkowane.

Drzewo przedstawione na rysunku 9.2(a) nie jest kopcem, bo nie jest to drzewo doskonałe. Natomiast jest to drzewo częściowo uporządkowane: następniki każdego wierzchołka mają etykiety większe od etykiety tego wierzchołka. Drzewo przedstawione na rysunku 9.2(b) jest drzewem doskonałym: do przedostatniego poziomu jest to pełne drzewo binarne, a liście na ostatnim poziomie są zgrupowane maksymalnie na lewo. Nie jest to jednak kopiec, ponieważ, np. węzeł z etykietą 4 ma oba następniki opatrzone etykietami mniejszymi od 4. Drzewo przedstawione na rysunku 9.2(c) jest kopcem, bo jest to drzewo doskonałe i częściowo uporządkowane.

Uwaga Przedstawione w tym wykładzie kopce są etykietowane zwykle liczbami naturalnymi i porządek £ jest zwykłym porządkiem w zbiorze liczb naturalnych. Nie jest to jednak obowiązująca reguła: etykiety mogą być elementami dowolnego zbioru liniowo uporządkowanego, a relacja £ może być dowolną relacją liniowego porządku. W szczególności, może to być relacja ³ w zbiorze liczb rzeczywistych.

Pytanie 1: Czy jest prawdą, że w kopcu długości ścieżek od korzenia do liści różnią się co najwyżej o 1?