Czym jest stos w kontekście programowania i jakie rodzaje stosów istnieją?

Kopiec (Heap) to obszar w pamięci operacyjnej używany do dynamicznej alokacji pamięci podczas działania programu.

Główne cechy:

• Pamięć jest przydzielana i zwalniana jawnie przez programistę (lub zbieracz śmieci).
• Nie ma ścisłej kolejności przydzielania/zwalniania bloków pamięci.
• Zarządzanie pamięcią jest bardziej skomplikowane niż na stosie, może prowadzić do fragmentacji i wycieków pamięci.

Rodzaje kopców (w kontekście struktur danych):

• Kopiec binarny (Binary Heap): Drzewo spełniające własność kopca. Dla każdego węzła (z wyjątkiem korzenia) jego wartość jest mniejsza lub większa od wartości rodzica.
  • Min Heap: Wartość rodzica jest zawsze mniejsza lub równa wartościom potomków. Minimalny element znajduje się w korzeniu.
  • Max Heap: Wartość rodzica jest zawsze większa lub równa wartościom potomków. Maksymalny element znajduje się w korzeniu.
• Kopiec binomialny (Binomial Heap): Kolekcja drzew binomialnych spełniających określone własności. Obsługuje efektywne operacje łączenia.
• Kopiec Fibonacciego (Fibonacci Heap): Struktura danych używana w algorytmach takich jak Dijkstra. Zapewnia bardziej efektywne amortyzowane czasy operacji w porównaniu z kopcem binarnym.
• Kopiec parowania (Pairing Heap): Prosta w implementacji struktura danych z dobrymi amortyzowanymi czasami.
• Kopiec lewostronny (Leftist Heap): Struktura danych ułatwiająca efektywne łączenie. Ważną własnością jest "ranga" lub "długość ścieżki zerowej", używana do szybkiego łączenia.

Te rodzaje kopców są używane w różnych algorytmach, takich jak sortowanie (Heap Sort), implementacja kolejek priorytetowych, algorytmy wyszukiwania najkrótszej ścieżki itp. Wybór konkretnego rodzaju kopca zależy od wymaganych operacji i ich efektywności czasowej.