Kopiec (informatyka)

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
Ujednoznacznienie Ten artykuł dotyczy informatyki. Zobacz też: inne znaczenia tego słowa.

Kopiec (ang. heap, tłumaczone też jako stóg lub sterta) – w informatyce 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 | edytuj kod]

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 | edytuj kod]

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 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 n, to ojciec ma ⌊n/2⌋ (np. dla 7 ojciec ma numer 3).
  • Jeśli ojciec ma numer n, to lewy potomek ma numer 2n, a prawy 2n+1.

Zastosowanie kopców[edytuj | edytuj kod]

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 / 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, tak długo jak są w kopcu 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 | edytuj kod]