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].

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:

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 ${\displaystyle \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)

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

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).

• kolejka priorytetowa
• sortowanie przez kopcowanie
• drzewo AVL
• teoria grafów

• Wizualizacja kopca binarnego