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
Jeżeli kopiec ma być kopcem zupełnym, wtedy dodatkowo spełnione muszą być warunki:
Właściwości kopców
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
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).