Kopiec – fiszki

Kopiec

Struktura danych w formie drzewa, w której każdy węzeł jest większy (lub mniejszy) od swoich dzieci.

Kopiec maksymalny

Rodzaj kopca, gdzie każdy węzeł jest większy lub równy swoim dzieciom.

Kopiec minimalny

Rodzaj kopca, w którym każdy węzeł jest mniejszy lub równy swoim dzieciom.

Zastosowanie kopca

Używane w algorytmie sortowania Heapsort oraz w implementacji kolejek priorytetowych.

Heapsort

Algorytm sortowania, który wykorzystuje kopiec do posortowania elementów w czasie O(n log n).

Operacja wstawiania

Dodaje nowy element do kopca, zachowując jego strukturę i własności.

Operacja usuwania

Usuwa element korzenia kopca i reorganizuje pozostałe, aby zachować właściwości kopca.

Właściwość kopca

Wszystkie elementy mogą być szybko dodawane i usuwane przy zachowaniu struktury.

Reprezentacja kopca

Może być reprezentowany jako tablica, gdzie indeksy rodziców i dzieci są określone matematycznie.

Różnica między kopcem a drzewem binarnym

Kopiec ma szczególne własności węzłów, podczas gdy drzewo binarne nie musi ich spełniać.

Kopiec a kolejka priorytetowa

Kopiec jest strukturą, która często implementuje kolejki priorytetowe, gdzie elementy są przetwarzane według priorytetu.

Uzupełnij zdanie: Największy element kopca maksymalnego to ___

korzeń kopca.

Kiedy stosować kopce?

Gdy potrzebne są szybkie operacje na najwyższych lub najniższych elementach.

Prawda czy fałsz: Heapsort jest stabilny.

Fałsz, ponieważ Heapsort nie zachowuje względnej pozycji równych elementów.

Uzupełnij zdanie: Kopiec może być użyty w ___

implementacji grafów, algorytmach Dijkstry.

Porównaj kopiec maksymalny i minimalny

Maksymalny zwraca największy element, a minimalny najmniejszy.