Kopiec binarny

Kopiec binarny

Kopiec binarny, znany również jako sterta, to tablicowa struktura danych, która reprezentuje drzewo binarne. W takim drzewie wszystkie poziomy z wyjątkiem ostatniego muszą być pełne, a liście na ostatnim poziomie są układane od lewej do prawej. Wyróżniamy dwa typy kopców: kopiec max, w którym wartość węzła jest mniejsza od wartości jego rodzica, oraz kopiec min, w którym wartość węzła jest większa od wartości rodzica.

Reprezentacja kopca w pamięci

Kopiec binarny jest przechowywany w pamięci jako tablica, zarządzana przez dwa parametry: length (rozmiar tablicy) oraz heap-size (rozmiar kopca). Korzeń drzewa znajduje się w pierwszej komórce tablicy. Indeksy lewego i prawego dziecka węzła i to odpowiednio 2i oraz 2i+1, a indeks rodzica węzła i można obliczyć jako $\backslash left\backslash lfloor\; \backslash frac\{i\}\{2\}\; \backslash right\backslash rfloor$.

Budowanie i naprawianie struktury kopca

W celu naprawienia struktury kopca używa się funkcji Heapify, która rekurencyjnie zamienia miejscami węzły, aby przywrócić właściwości kopca. Pseudokod funkcji wygląda następująco:

funkcja Heapify(a):
    largest := a
    jeśli 2a <= size i H[2a] > H[largest], to
        largest := 2a
    jeśli 2a + 1 <= size i H[2a + 1] > H[largest], to
        largest := 2a + 1
    jeśli largest != a, to
        zamień H[largest] z H[a]
        wywołaj Heapify(largest)

Aby zbudować kopiec, wykorzystujemy procedurę Build-Heap, która przetwarza wszystkie węzły:

procedura Build-Heap:
    dla i z zakresu size .. 1:
        wywołaj Heapify(i)

Dodawanie nowych wierzchołków

Dodanie nowego wierzchołka do kopca polega na umieszczeniu go na końcu i „przepychaniu” go w górę, aż do przywrócenia warunku kopca. Pseudokod dodawania wygląda następująco:

funkcja Insert(a):
    size := size + 1
    child := size
    H[child] := a
    dopóki child > 1 i H[child] > H[child/2], wykonuj
        zamień H[child] z H[child/2]
        child := child / 2

Usuwanie wierzchołka ze szczytu kopca

Aby usunąć wierzchołek ze szczytu kopca, przestawiamy ostatni wierzchołek na szczyt i „spychamy” go w dół, zamieniając miejscami z większymi dziećmi, aż do przywrócenia warunku kopca. Proces ten również ma złożoność O(logn).

Podsumowanie

Kopiec binarny jest efektywną strukturą danych do zarządzania hierarchicznymi danymi. Operacje wstawiania i usuwania mają logarytmiczną złożoność czasową, co czyni go przydatnym w wielu zastosowaniach, takich jak sortowanie czy zarządzanie priorytetami.