Kopiec (informatyka)

Kopiec – Definicja

Kopiec to struktura danych oparta na drzewie, w której istnieje ustalona relacja między wartościami rodzica a wartościami potomków. W przypadku kopca maksymalnego wartość rodzica jest nie mniejsza niż wartości jego potomków.

Kopiec Zupełny

Aby kopiec był uznawany za kopiec zupełny, musi spełniać dodatkowe warunki:

• Drzewo jest prawie pełne, co oznacza, że liście występują na ostatnim oraz ewentualnie przedostatnim poziomie, ale tylko wtedy, gdy ostatni poziom nie jest w pełni wypełniony.
• Liście na ostatnim poziomie są uporządkowane od lewej do prawej.

Właściwości Kopców

W kopcu, w przypadku relacji mniejszości, na szczycie znajduje się węzeł z największym kluczem. Kopiec binarny można efektywnie zaimplementować w tablicy, numerując elementy od szczytu kopca, zaczynając od 1 i poruszając się od lewej do prawej. Dostęp do rodzica oraz potomków realizuje się w następujący sposób:

• Jeśli potomek ma numer $n$, to jego ojciec ma numer $n/2$.
• Jeśli ojciec ma numer $n$, to lewy potomek ma numer $2n$, a prawy $2n+1$.

Zastosowanie Kopców

Kopce znajdują zastosowanie w implementacji kolejek priorytetowych, umożliwiając szybki dostęp do wierzchołka o największej lub najmniejszej wartości. Drugim popularnym zastosowaniem kopców jest sortowanie. Wstawiając nowe wierzchołki do kopca, uzyskujemy uporządkowanie danych, a następnie usuwając obiekty ze szczytu kopca, otrzymujemy posortowaną sekwencję. Ta metoda nazywana jest sortowaniem przez kopcowanie (ang. heapsort).