Czym jest stos?

Kopiec (heap) to specjalna struktura danych w postaci drzewa, która spełnia własność kopca. Własność ta mówi, że dla każdego wierzchołka, oprócz korzenia, wartość klucza tego wierzchołka powinna być w określonym stosunku do wartości klucza jego rodzica. Istnieją dwa główne typy kopców:

• Kopiec maksymalny (Max-heap): Wartość klucza każdego wierzchołka nie jest mniejsza od wartości kluczy jego dzieci. Maksymalny element znajduje się na szczycie.
• Kopiec minimalny (Min-heap): Wartość klucza każdego wierzchołka nie jest większa od wartości kluczy jego dzieci. Minimalny element znajduje się na szczycie.

Kopiec jest zwykle implementowany jako tablica, co umożliwia efektywny dostęp do elementów i wykonywanie operacji. Związek między rodzicami a dziećmi w tablicy jest następujący:

• Dla elementu o indeksie i (licząc od 0), jego lewy potomek znajduje się pod indeksem 2i + 1.
• Jego prawy potomek znajduje się pod indeksem 2i + 2.
• Jego rodzic znajduje się pod indeksem floor((i - 1) / 2).

Podstawowe operacje na kopcu:

• Wstawianie: Dodanie nowego elementu. Czas wykonania O(log n), gdzie n to liczba elementów.
• Wydobycie maksimum / minimum: Usunięcie i zwrócenie maksymalnego (w kopcu maksymalnym) lub minimalnego (w kopcu minimalnym) elementu. Czas wykonania O(log n).
• Heapify (Budowa kopca): Przekształcenie dowolnej tablicy w kopiec. Czas wykonania O(n).

Kopce są używane w algorytmach sortowania (np. sortowanie przez kopiec), w kolejach priorytetowych oraz w algorytmach wyszukiwania najkrótszych ścieżek (np. algorytm Dijkstry).