Struktury danych/Kopce

Spis treści
Wstęp	Wstęp - Konwencje
Struktury danych	Podstawy - Tablice - Listy - Stosy - Kolejki - Drzewa - Zbiory - Kopce - Find-Union - Tablice z haszowaniem - Grafy
Dodatki	Złożoność obliczeniowa - Implementacje w C++ - Implementacje w Pascalu - Bibliografia - Dla twórców podręcznika

Kopiec

(ang. heap) Jest to pewna modyfikacja struktury drzewa. Do drzewa dodano dodatkowy warunek – stałą relację rodzica z dzieckiem, np. może to być – wartość rodzica jest nie mniejsza od wartości potomka.

Pod pojęciem (binarnego) kopca zupełnego definiuje się kopiec, który dodatkowo jest prawie pełnym drzewem binarnym, to znaczy, że to drzewo będzie wypełniane poziomami, ale ostatni poziom jest niekoniecznie wypełniony do końca. Zaraz wytłumaczymy co to dokładnie oznacza.

Kopce występują w dwóch odmianach zależnych od tzw. własności kopca – tj. warunku jaki spełniają poszczególne węzły między sobą. W kopcu typu max spełniona jest własność typu max. W przypadku kopca typu min analogicznie spełniona jest własność typu min.

Najważniejszą własnością jaką zapewnia korzystanie ze struktury prawie pełnego binarnego drzewa jest fakt, że zawsze będzie ona zrównoważona. Oznacza to, że nie dojdzie do sytuacji, w której może się okazać, że dostęp do elementów będzie miał czas $O(n)$ jak w przypadku listy, czy źle zbalansowanego drzewa BST. Dostęp do elementu będzie miał zawsze złożoność czasową rzędu $O(h)$ gdzie nasze h to wysokość kopca. Jednak w tym wypadku zapewniamy sobie (korzystając z kopca zupełnego) to że h będzie rzędu $O(log(n))$. Z tego wynika, że przechodzenie poszczególnych ścieżek w kopcu (zależne od jego wysokości) będzie asymptotycznie operacją logarytmiczną.

Implementacja

Do reprezentacji kopca korzysta się z tablicy. Każdy węzeł drzewa odpowiada pewnemu elementowi tablicy. Drzewo jest pełne na wszystkich poziomach z wyjątkiem, być może najniższego, który jest wypełniony od lewej do pewnego miejsca (zupełność). Ważne jest to, żeby sobie uzmysłowić, że taka implementacja daje nam bardzo ciekawe i użyteczne zależności między indeksami w tablicy i poszczególnymi węzłami drzewa, które jest reprezentowane przez tą tablicę. Najpierw jednak wyszczególnijmy jakie operacje możemy wykonać na kopcu.

Kopiec typu max

• PARENT(i: indeks węzła) operacja zwracająca rodzica dla danego węzła.
• LEFT-CHILD(i: indeks węzła) zwraca lewe dziecko danego węzła.
• RIGHT-CHILD(i:indeks węzła) zwraca prawe dziecko danego węzła.
• MAX(S:zbiór) zwraca największą wartość w kopcu nie zmieniając struktury
• EXTRACT-MAX(S:zbiór) zwraca największą wartość w kopcu usuwając go ze zbioru w sposób, który zachowuje jego własności
• UPHEAP(i: indeks węzła) przywraca własność kopca dla wartości z indeksu i, która się zwiększyła na ścieżce od i-tego elementu do korzenia
• DOWNHEAP(i: indeks węzła) przywraca własność kopca dla wartości z indeksu i, która się zmniejszyła na ścieżce od i-tego elementu do korzenia
• MAX-HEAPIFY(S:zbiór, i:indeks węzła) procedura służąca do utrzymywania własności kopca typu max.
• BUILD-HEAP(S: zbiór) dla tablicy S elementy zostaną uporządkowane tak by dla każdego został spełniony warunek kopca.

Na rysunku obok widać przykładowy kopiec typu max, przy każdym węźle zaznaczony został odpowiadający mu indeks z tablicy. Korzystając z tego rysunku pokażemy teraz jak działają pierwsze trzy procedury, które definiujemy dla kopca.

Parent

Ta procedura ma zwracać wskaźnik na rodzica danego elementu. Kod tej funkcji napisany w C++ mógłby wyglądać na przykład tak:

int parent(int i){
    return i/2;// ta funkcja zadziała dla tablic indeksowanych jak na rysunku powyżej - zaczynając od 1
}

Zastanówmy się teraz dlaczego jest to poprawne. W C++ dla typu całkowitoliczbowego operator dzielenia zwraca również liczbę całkowitą, z tego powodu dla dwóch różnych elementów będzie zwracana ta sama wartość. Weźmy pod uwagę kopiec z rysunku powyżej. Biorąc element o indeksie 8 funkcja parent zwróci 4, co się zgadza, bo patrząc na grafikę możemy to od razu zauważyć, wywołując ją z argumentem 9 również otrzymamy poprawny indeks rodzica.

Left-child

int left_child(int i){
    return 2*i; // ta funkcja zadziała dla tablic indeksowanych jak na rysunku powyżej - zaczynając od 1
}

Sprawdźmy teraz, czy faktycznie podany tutaj wzór zadziała. Dla $15$ o indeksie 5 lewym dzieckiem będzie wartość z pod indeksu 10, czyli $3$. Wszystko się zgadza.

Right-child

int right_child(int i){
    return 2*i+1; // ta funkcja zadziała dla tablic indeksowanych jak na rysunku powyżej - zaczynając od 1
}

W tym wypadku funkcja wygląda analogicznie do left-child z tym, że dodajemy jedynkę. Patrząc na powyższą grafikę można zauważyć, że ma to sens i faktycznie działa poprawnie.

Max-heapify

template <typename T>
void max_heapify(T[] heap, int i){
int l = left_child(i);
int r = right_child(i);
int largest = i;
if (l <= size(heap) and heap[l] > heap[i])
    largest = l;
if (r<=size(heap) and heap[r] > heap[largest])
    largest = r;
if (largest != i) {
    swap(heap[i], heap[largest]); //zamień największą wartość z wartością z pod indeksu i
    max_heapify(heap, largest);
}
}

Build-heap

template <typename T>
void build_heap(T A[],int s){ // A- tablica do "skopcowania", s-wielkość kopca (ilość faktycznych elementów w tablicy)
    int r = s/2; /*poprzednio było iterowanie od s do 0, lecz optymalniej jest iterować od s/2, ponieważ dopiero ten element ma dzieci*/ 
    while(r !=0){
    max_heapify(A,r);
    r=r-1;
    }
}

Upheap

template <typename T>
void upheap(T[] heap, int i){
while (i>1 and heap[parent(i)] < heap[i]) {
    swap(heap[i],heap[parent(i)]);
    i=i/2;
}
}

Ćwiczenia

Podstawowe

Ćwiczenie 1: Napisz wszystkie funkcje podane powyżej dla tablic indeksowanych od 0 do n-1 dla tablicy wielkości n.