Kopiec (informatyka)

Kopiec (ang. heap, tłumaczone też jako stóg lub sterta) – struktura danych oparta na drzewie, w której wartości potomków węzła są w stałej relacji z wartością rodzica (na przykład wartość rodzica jest nie mniejsza niż wartości jego potomka).

Kopiec zupełny

edytuj

Jeżeli kopiec ma być kopcem zupełnym, wtedy dodatkowo spełnione muszą być warunki:

  • drzewo jest prawie pełne, tzn. liście występują na ostatnim i ewentualnie przedostatnim poziomie w drzewie (tylko gdy ostatni poziom nie jest całkowicie wypełniony),
  • liście na ostatnim poziomie są spójnie ułożone od strony lewej do prawej.

Właściwości kopców

edytuj

Jeśli przyjętą relacją między wartością potomka a wartością rodzica będzie relacja mniejszości, wówczas na szczycie znajdzie się węzeł z największym kluczem.

W przypadku zupełnego kopca binarnego, łatwo zaimplementować kopiec w tablicy, według poniższego schematu (dla innych kopców istnieją podobne techniki). Numerując kolejne elementy począwszy od szczytu kopca od 1, a następnie od lewej do prawej, na każdym kolejnym poziomie kopca możemy łatwo uzyskać dostęp do potomka lewego lub prawego, albo ojca, przy czym:

  • Jeśli potomek ma numer   to ojciec ma   (np. dla 7 ojciec ma numer 3). Używamy przy tym operacji dzielenia całkowitego.
  • Jeśli ojciec ma numer   to lewy potomek ma numer   a prawy  

Zastosowanie kopców

edytuj

Kopce mogą być używane do implementacji kolejek priorytetowych, ponieważ ustalenie odpowiedniej relacji umożliwia bezpośredni dostęp do wierzchołka o największej lub najmniejszej wartości z danego zbioru zapisanego w kopcu.

Drugie częste zastosowanie struktury kopca to sortowanie. Wstawianie nowych wierzchołków do kopca porządkuje je. Następnie możemy zdejmować obiekty ze szczytu kopca, dopóki w kopcu są jakieś obiekty. Otrzymamy wówczas ciąg obiektów uporządkowany według klucza. Na tej zasadzie działa procedura sortowania przez kopcowanie (ang. heapsort).

Zobacz też

edytuj