Kopiec binarny (, 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óżnia się 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.
Reprezentacja kopca binarnego w pamięci thumb|250px|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
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 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: wstaw wierzchołek na pozycję n+1 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 usuń wierzchołek ze szczytu kopca przestaw ostatni wierzchołek z pozycji n na szczyt kopca; niech k oznacza jego klucz 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).
Zobacz też kolejka priorytetowa sortowanie przez kopcowanie drzewo AVL teoria grafów
Przypisy
Linki zewnętrzne Wizualizacja kopca binarnego
Kategoria:Struktury danych Kategoria:Drzewa (informatyka)