Kopiec binarny

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Kopiec binarny (czasem używa się też określenia sterta) (ang. binary heap) - tablicowa struktura danych reprezentująca drzewo binarne, którego wszystkie poziomy z wyjątkiem ostatniego muszą być pełne. W przypadku, gdy ostatni poziom drzewa nie jest pełny, liście ułożone są od lewej do prawej strony drzewa. Wyróżniamy dwa rodzaje kopców binarnych: kopce binarne typu max w których wartość danego węzła niebędącego korzeniem jest zawsze mniejsza niż wartość jego rodzica oraz kopce binarne typu min w których wartość danego węzła niebędącego korzeniem jest zawsze większa niż wartość jego rodzica[1].

Reprezentacja kopca binarnego w pamięci[edytuj | edytuj kod]

Rysunek 1: Przykład niepełnego drzewa binarnego

Kopiec binarny przechowywany jest w pamięci w postaci tablicy opisanej dwoma parametrami: parametrem length przechowującego informacje o wielkości całej tablicy oraz parametrem heap-size, który przechowuje informacje o wielkości kopca binarnego. Korzeń drzewa przechowywany jest zawsze w pierwszej komórce tablicy. Dla drzewa zwizualizowanego na rysunku 1 kopiec binarny wygląda następująco:

Indeks 1 2 3 4 5 6 7 8 9 10
Klucz 20 16  8 10 15  2  5  7  6  3

Na pierwszej pozycji znajduje się korzeń. Indeksy lewego i prawego syna węzła i to odpowiedni 2i oraz 2i+1. Indeks rodzica węzła i niebędącego korzeniem to \left\lfloor \frac{i}{2} \right\rfloor[1]

Budowanie i naprawianie struktury kopca w pseudokodzie:

Naprawianie struktury kopca

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

Budowanie kopca

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

Dodawanie nowych wierzchołków[edytuj | edytuj kod]

Załóżmy, że kopiec składa się z n elementów, zaś elementy uporządkowane są od największych (warunek kopca brzmi więc: każdy element jest większy od swoich dzieci). Dodawany wierzchołek ma klucz równy k:

  1. wstaw wierzchołek na pozycję n+1
  2. zamieniaj pozycjami z rodzicem (przepychaj w górę) aż do przywrócenia warunku kopca (czyli tak długo, aż klucz rodzica jest większy niż k, lub element dotrze na pozycję 1)

Dodawanie nowego wierzchołka w pseudokodzie:

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

Usuwanie wierzchołka ze szczytu kopca[edytuj | edytuj kod]

  1. usuń wierzchołek ze szczytu kopca
  2. przestaw ostatni wierzchołek z pozycji n na szczyt kopca; niech k oznacza jego klucz
  3. spychaj przestawiony wierzchołek w dół, zamieniając pozycjami z większymi z dzieci, aż do przywrócenia warunku kopca (czyli aż dzieci będą mniejsze od k lub element dotrze na spód kopca)

Zarówno wstawianie jak i usuwanie obiektów ze szczytu kopca ma złożoność O(logn).

Przypisy

  1. 1,0 1,1 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Wprowadzenie do algorytmów. Wydawnictwa Naukowo-Techniczne, 2007, s. 124-126.

Zobacz też[edytuj | edytuj kod]