Czym jest stos (w kontekście struktur danych)?

Kopiec (heap) to specjalistyczne drzewo, które jest używane jako struktura danych. Główna właściwość kopca to częściowa uporządkowanie: dla każdego wierzchołka warunek jest taki, że wartość wierzchołka rodzica jest większa lub równa wartości dowolnego z jego dzieci (max-heap) lub mniejsza lub równa (min-heap).

Kluczowe cechy:

• Drzewo binarne: Najczęściej implementowane jako drzewo binarne, gdzie każdy węzeł ma nie więcej niż dwóch potomków.
• Drzewo binarne pełne: Na wszystkich poziomach, oprócz być może ostatniego, drzewo jest w pełni wypełnione. Węzły na ostatnim poziomie są wypełniane od lewej do prawej. Pozwala to na efektywne przechowywanie kopca w formie tablicy.
• Właściwość kopca:
  • Max-heap: Wartość każdego węzła jest większa lub równa wartościom jego potomków. Maksymalny element zawsze znajduje się na korzeniu.
  • Min-heap: Wartość każdego węzła jest mniejsza lub równa wartościom jego potomków. Minimalny element zawsze znajduje się na korzeniu.

Podstawowe operacje na kopcu:

• Wstawianie elementu: Dodanie nowego elementu i utrzymanie właściwości kopca.
• Usuwanie elementu: Usunięcie elementu korzenia (maksymalnego lub minimalnego, w zależności od typu kopca) i utrzymanie właściwości kopca.
• Tworzenie kopca: Budowa kopca z tablicy elementów.

Zastosowania kopca:

• Sortowanie: Algorytm sortowania przez kopiec (Heapsort).
• Kolejki z priorytetem: Efektywna implementacja kolejek, w których elementy są przetwarzane w kolejności priorytetu.
• Algorytmy wyszukiwania: Na przykład, wyszukiwanie elementu k-tego według wartości.
• Algorytmy na grafach: Na przykład, algorytm Dijkstry.

Reprezentacja kopca w tablicy:

Ponieważ kopiec jest pełnym drzewem binarnym, można go efektywnie przechowywać w tablicy bez użycia wskaźników.

• Jeśli węzeł znajduje się pod indeksem i, jego lewy potomek znajduje się pod indeksem 2*i + 1.
• Jego prawy potomek znajduje się pod indeksem 2*i + 2.
• Jego rodzic znajduje się pod indeksem (i - 1) / 2.

# Przykład reprezentacji min-kopca w formie tablicy
heap_array = [10, 15, 20, 17, 25, 30]

# Korzeń: heap_array[0] = 10
# Lewy potomek korzenia: heap_array[2*0 + 1] = heap_array[1] = 15
# Prawy potomek korzenia: heap_array[2*0 + 2] = heap_array[2] = 20
# Rodzic elementu na indeksie 3 (17): heap_array[(3-1)//2] = heap_array[1] = 15