Loading AI tools
Z Wikipedii, wolnej encyklopedii
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).
Jeżeli kopiec ma być kopcem zupełnym, wtedy dodatkowo spełnione muszą być warunki:
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:
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).
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.