Kopiec binarny (ang. binary heap, czasem używa się też określenia sterta) – 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

 
Rysunek 1: Przykład niepełnego drzewa binarnego typu max

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  [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

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

  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 edytuj

  1. a b 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

Linki zewnętrzne edytuj