Podręcznik

Sterta (ang. heap) to specjalna struktura danych w postaci drzewa binarnego, która spełnia warunek porządku kopca. Oznacza to, że w kopcu maksymalnym (ang. max-heap) każdy rodzic ma wartość większą lub równą swoim dzieciom, natomiast w kopcu minimalnym (ang. min-heap) każdy rodzic ma wartość mniejszą lub równą swoim dzieciom. Dzięki tej właściwości sterta pozwala w bardzo krótkim czasie zidentyfikować element o największym lub najmniejszym priorytecie, co czyni ją idealną podstawą do implementacji kolejki priorytetowej. 

Jednym z podstawowych typów struktur danych są właśnie kolejki priorytetowe, które przechowują elementy zbioru, na którym zdefiniowana jest relacja porządku. Każdemu elementowi przypisuje się klucz (priorytet), według którego ustalana jest kolejność operacji. W przeciwieństwie do zwykłej kolejki, gdzie elementy są usuwane w kolejności ich wstawienia (FIFO), w kolejce priorytetowej elementy są zdejmowane na podstawie wartości klucza. Wyróżniamy dwa główne typy takich kolejek: kolejki typu max, gdzie usuwany jest element o największym priorytecie, oraz kolejki typu min, w których priorytet ma wartość najmniejsza.

Kolejka priorytetowa musi być zaimplementowana w taki sposób, aby można było wykonywać na niej niżej wymienione operacje:

• Insert(S, x) – wstawienie elementu x do kolejki S
• FindMax(S) – poszukiwanie w kolejce S elementu o największym kluczu; funkcja zwraca ten element jako wynik
• DelMax(S) – usunięcie z kolejki S elementu o największym kluczu; funkcja zwraca ten element jako wynik

Choć kolejkę priorytetową można zaimplementować w oparciu o listę lub tablicę, to jednak takie rozwiązania są nieefektywne, zwłaszcza przy dużych zbiorach danych. Zdecydowanie lepszą alternatywą jest wykorzystanie struktury sterty, która pozwala na wykonywanie operacji w czasie logarytmicznym względem liczby elementów. Sterta jest najczęściej implementowana w formie tablicy, w której dla każdego elementu o indeksie i jego lewy potomek znajduje się na pozycji 2i + 1, a prawy potomek na pozycji 2i + 2. Dzięki temu możliwa jest efektywna nawigacja po strukturze bez potrzeby tworzenia jawnych węzłów drzewa. Ta reprezentacja umożliwia również przekształcenie dowolnej tablicy w stertę w czasie liniowym. W literaturze anglojęzycznej częściej wykorzystuje się pojęcie kopiec (ang. Heap). Są to pojęcia tożsame i można nazw używać zamiennie. Na rysunku poniżej przedstawiono przykładowy kopiec wraz z deklaracją w postaci tablicy jednowymiarowej.


Jeżeli na danym poziomie wszystkie miejsca są zapełnione oznacza to że drzewo jest pełne na danym poziomie. Jedynie ostatni poziom może nie być wypełniony do końca. Widzimy też, że kopiec jest często implementowany jako tablica jednowymiarowa, w której elementy drzewa binarnego zapisywane są kolejno w taki sposób, by zachować zależności rodzic–dziecko. Dzięki temu możliwe jest odwzorowanie struktury drzewa bez użycia wskaźników, a dostęp do poszczególnych węzłów oraz ich potomków może być realizowany za pomocą prostych obliczeń indeksów. Mianowicie, jeśli interesujący nas węzeł znajduje się w tablicy pod indeksem i, to:

•  indeks jego ojca (rodzica) to ⌊i / 2⌋, czyli część całkowita z połowy wartości i (dla i > 1), 
•  indeks lewego potomka wynosi 2 * i, 
•  indeks prawego potomka wynosi 2 * i + 1.

Dzięki tej właściwości, poruszanie się po strukturze drzewa zaimplementowanej jako tablica jest bardzo szybkie i nie wymaga stosowania złożonych struktur danych. W praktyce indeksowanie zaczyna się najczęściej od i = 1 (pomijając komórkę 0) w celu uproszczenia obliczeń, choć w niektórych implementacjach używa się również indeksowania od 0, z odpowiednio przesuniętymi wzorami.
Dzięki wykorzystaniu tej definicji możemy skonstruować algorytm, który będzie sortował wartości w tablicy. Wiemy, że zawsze w korzeniu drzewa kopca będzie przechowywana największa wartość. Jeżeli będziemy pobierać za każdym razem korzeń drzewa i umieszczać w tablicy posortowanych liczb to otrzymamy algorytm sortowania przez kopcowanie. Oczywiście brakuje nam jeszcze wiedzy w jaki sposób po pobraniu wartości korzenia drzewa przywrócić ponownie jego własności. Jednym z mechanizmów utrzymujących strukturę sterty jest metoda przywracania własności kopca (ang. heapify). Jej zadaniem jest upewnienie się, że poddrzewo o korzeniu na danym indeksie i spełnia warunek kopca. W przypadku kopca maksymalnego oznacza to, że element znajdujący się na pozycji i powinien być nie mniejszy niż jego dzieci. Jeżeli warunek ten nie jest spełniony, to element i należy zamienić z większym z jego dwóch synów, co powoduje tzw. „spłynięcie w dół” (ang. sift down) danego elementu w hierarchii drzewa. Po takiej zamianie konieczne jest sprawdzenie poprawności struktury dla nowego położenia tego elementu, czyli rekursywne wywołanie funkcji dla odpowiedniego poddrzewa.

// Funkcja przywracająca własność kopca dla poddrzewa o korzeniu i
void heapify(vector<int>& T, int n, int i) {
    int largest = i;            // Zakładamy, że korzeń jest największy
    int left = 2 * i + 1;       // Indeks lewego dziecka
    int right = 2 * i + 2;      // Indeks prawego dziecka

    // Jeśli lewe dziecko jest większe niż korzeń
    if (left < n && T[left] > T[largest])
        largest = left;

    // Jeśli prawe dziecko jest większe niż największy dotąd
    if (right < n && T[right] > T[largest])
        largest = right;

    // Jeśli największy nie jest korzeniem, zamień i kontynuuj
    if (largest != i) {
        swap(T[i], T[largest]);
        heapify(T, n, largest);  // Rekurencyjnie przywracaj własność kopca
    }
}

Widzimy, że w przykładowej implementacji rekurencyjnie wywoływana jest funkcja przywracania własności kopca. Proces ten jest powtarzany aż do momentu, gdy żadne dalsze zamiany nie będą potrzebne i kopiec odzyska swoją właściwość.

// Pobiera największy element z kopca (korzeń) i przywraca strukturę
int extractMax(vector<int>& heap, int& size) {
    if (size <= 0) throw out_of_range("Sterta jest pusta.");

    int maxElement = heap[0];  // największy element (korzeń)

    heap[0] = heap[size - 1];  // przenosimy ostatni element na początek
    size--;                    // zmniejszamy rozmiar kopca

    heapify(heap, size, 0);    // przywracamy własność kopca od korzenia

    return maxElement;
}

Poniżej przedstawiono przykład rysunkowy pobierania wartości maksymalnej z drzewa, a więc jego korzenia.

Kolejną metodą przydatną do operowania na kopcu jest dodawanie do niego elementów. Dodawanie nowego elementu do kolejki priorytetowej opartej na kopcu maksymalnym polega na wstawieniu go jako nowego liścia na najniższym, najbardziej prawym wolnym miejscu w drzewie (czyli na końcu tablicy reprezentującej stertę). Jednak po takim dodaniu własność kopca może być naruszona, jeśli nowy element ma większy klucz niż jego ojciec. W takiej sytuacji należy przywrócić poprawną strukturę kopca poprzez tzw. „wynurzanie się” elementu – czyli przesuwanie go w górę drzewa przez zamiany z jego rodzicem aż do momentu, gdy znajdzie się w odpowiednim miejscu (lub zostanie korzeniem). Ten proces można przeprowadzić na dwa sposoby:

void insert(vector<int>& heap, int& size, int value) {
    size++;
    int i = size - 1;
    heap[i] = value;

    while (i > 0 && heap[i] > heap[(i - 1) / 2]) {
        swap(heap[i], heap[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

W innej wersji nie zamieniamy elementów tylko przesuwamy ojców w dół. Gdy znajdziemy odpowiednie miejsce, wpisujemy nowy element w ostatnim kroku. W praktyce ta metoda może być szybsza, ponieważ zmniejsza liczbę operacji kopiowania danych.

void insert(vector<int>& heap, int& size, int value) {
    size++;
    int i = size - 1;

    // Znalezienie miejsca na nowy element przez przesuwanie ojców w dół
    while (i > 0 && value > heap[(i - 1) / 2]) {
        heap[i] = heap[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    heap[i] = value;
}

Poniżej przedstawiono przykład rysunkowy pokazujący wstawienie nowej wartości do kopca oraz przywróceniu jego własności.

Skoro poznaliśmy już procedurę przywracania własności kopca, możemy przejść do pytania, w jaki sposób zbudować stertę z danych znajdujących się w tablicy, o których nic nie wiemy – to znaczy danych, które nie są w żaden sposób uporządkowane i nie spełniają warunku kopca. Co istotne, elementy tablicy tworzą logicznie strukturę drzewa binarnego, lecz bardzo rzadko jest ona od razu stertą. Aby utworzyć poprawną strukturę kopca, należy zadbać o to, by każde z poddrzew tej struktury spełniało własność kopca – a więc by każdy węzeł był większy (w przypadku kopca maksymalnego) od swoich dzieci. Pomysł polega na zastosowaniu metody przywrocWlasnoscKopca (heapify) dla każdego węzła wewnętrznego, zaczynając od najniższego poziomu drzewa, aż po korzeń. Ponieważ liście są już jednoelementowymi drzewami, które z definicji są kopcami, nie wymagają przetwarzania. Dlatego wystarczy rozpocząć od ostatniego węzła, który posiada dzieci, czyli od indeksu ⌊n/2⌋ − 1 (gdzie n to liczba elementów w tablicy), i wykonywać heapify w kolejnych krokach dla wszystkich poprzedzających go indeksów, aż do 0. W ten sposób, przekształcając najpierw najmniejsze poddrzewa, a następnie coraz większe, aż do całego drzewa, otrzymujemy strukturę spełniającą warunek kopca. Poniżej zamieszczony jest kod C++ do budowy kopca z tablicy zawierające liczby w dowolnej kolejności.

// Buduje kopiec maksymalny z nieuporządkowanej tablicy
void buildMaxHeap(vector<int>& T) {
    int n = T.size();

    // Wywołujemy heapify od ostatniego rodzica do korzenia
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(T, n, i);
    }
}

Po zdefiniowaniu podstawowych operacji na kopcu możemy przejść do sortowania przez kopcowanie. Sortowanie kopcowe to algorytm sortowania oparty na strukturze kopca, który działa w dwóch głównych fazach. W pierwszej fazie, z danych wejściowych zapisanych w tablicy T, budowany jest kopiec maksymalny. Oznacza to, że największy element zbioru trafia na początek tablicy, czyli do korzenia kopca. W drugiej fazie rozpoczyna się właściwe sortowanie. Największy element, znajdujący się w korzeniu, zostaje zamieniony miejscami z ostatnim elementem kopca (czyli z węzłem o największym indeksie). W ten sposób największy element „odpada” z kopca i trafia na ostateczne miejsce w tablicy wynikowej. Następnie rozmiar kopca zostaje logicznie zmniejszony o 1, a na pozostałej części tablicy ponownie przywracana jest własność kopca. Proces ten – polegający na pobieraniu największego elementu z kopca i umieszczaniu go na końcu – jest wykonywany iteracyjnie aż do momentu, gdy w kopcu pozostaną tylko dwa elementy. Wówczas wystarczy ostatnia zamiana miejsc między nimi, aby cała tablica była już w pełni posortowana w porządku rosnącym. Algorytm ten nie wymaga dodatkowej pamięci, działa w miejscu, a jego złożoność czasowa wynosi O(n log n) niezależnie od danych wejściowych.