| Kopiec (Heap) |
Kopiec - zupełne drzewo binarne, w którego węzłach znajdują się elementy reprezentowanego multizbioru (elementy mogą się powtarzać) S i jest spełniony warunek kopca: jeśli węzeł x jest następnikiem węzła y, to element w węźle x jest nie większy niż element w węźle y.
Własności kopca:
| Reprezentacja kopca w tablicy |
Kopiec może być reprezentowany w tablicy. Obowiązują wówczas następujące zależności:
|
indeks
|
0 | 1 | 2 | 3 | 4 | 5 | 6 |
|
element kopca
|
25 | 12 | 5 | 7 | 8 | 1 |
| Wstawianie elementów - insert |
Wstawienie elementu x do kopca polega na umieszczeniu elementu w pierwszym
wolnym miejscu i przywróceniu zachodzenia warunku kopca, jeśli wstawiony
element jest większy niż w poprzedniku. Aby przywrócić zachodzenie warunku,
należy przesuwać wstawiany element w kierunku korzenia (operacja upheap),
w poszukiwaniu miejsca gdzie warunek kopca będzie spełniony.
| Usunięcie największego - deletemax |
Aby usunąć największy element z kopca należy usunąć element z korzenia,
zaś na jego miejsce wstawić ostatni element (o największym indeksie) kopca.
Następnie należy przywrócić warunek kopca przesuwając element do dołu (operacja
downheap).
| Sortowanie - heapsort |
Sortowanie polega na n-krotnym wywołaniu funkcji deletemax, gdzie n
jest liczbą elementów kopca.
| Literatura |