Kopce binarne (min-heap, max-heap)

1. Czym jest kopiec binarny?

Kopiec binarny (binary heap) to zupełne drzewo binarne z właściwością kopca.

1.1. Właściwość kopca:

Min-Heap: - Każdy rodzic ≤ swoje dzieci - Najmniejszy element w korzeniu

Max-Heap: - Każdy rodzic ≥ swoje dzieci - Największy element w korzeniu

1.2. Wizualizacja:

Min-Heap:                Max-Heap:
       1                        100
      / \                      /  \
     3   2                   90    80
    / \  /                  / \   /
   5  4 10                 50 70 60

✅ Każdy rodzic ≤ dzieci    ✅ Każdy rodzic ≥ dzieci
✅ Min (1) w korzeniu       ✅ Max (100) w korzeniu

2. Zupełne drzewo binarne

Kluczowa właściwość: Kopiec to zupełne drzewo binarne.

2.1. Co to znaczy "zupełne"?

✅ Zupełne drzewo:
       1
      / \
     2   3
    / \  /
   4  5 6

- Wszystkie poziomy wypełnione (oprócz ostatniego)
- Ostatni poziom wypełniany od lewej

❌ NIE zupełne:
       1
      / \
     2   3
      \   \
       5   6

- Ostatni poziom nie od lewej!

2.2. Dlaczego "zupełne"?

Bo możemy reprezentować kopiec jako tablicę! 🎉

3. Reprezentacja kopca jako tablica

3.1. Mapowanie drzewo → tablica:

Drzewo:
       1
      / \
     3   2
    / \  /
   5  4 10

Tablica (indeks od 0):
[1, 3, 2, 5, 4, 10]
 0  1  2  3  4  5

Index:  0   1   2   3   4   5
Level:  0   1   1   2   2   2

3.2. Wzory na indeksy:

Dla węzła na indeksie i:

3.3. Przykład:

Tablica: [1, 3, 2, 5, 4, 10]

Węzeł i=1 (wartość 3):
- parent(1) = (1-1)//2 = 0 → wartość 1 ✅
- left_child(1) = 2*1+1 = 3 → wartość 5 ✅
- right_child(1) = 2*1+2 = 4 → wartość 4 ✅

       1 (i=0)
      / \
   3(i=1) 2(i=2)
   / \    /
5(i=3) 4(i=4) 10(i=5)

4. Implementacja Min-Heap

4.1. Klasa bazowa:

5. Operacja: Heapify Up (Bubble Up)

Użycie: Po wstawieniu nowego elementu na koniec.

5.1. Idea:

1. Wstaw element na koniec
2. Porównaj z rodzicem
3. Jeśli mniejszy od rodzica → zamień
4. Powtarzaj aż:
   - Element ≥ rodzic (OK)
   - Element jest korzeniem

5.2. Wizualizacja:

Min-Heap: [1, 3, 2, 5, 4, 10]
Wstaw: 0

Krok 1: Dodaj na koniec
[1, 3, 2, 5, 4, 10, 0]
                    ↑

Krok 2: Porównaj z rodzicem (2)
0 < 2 → ZAMIEŃ

[1, 3, 0, 5, 4, 10, 2]
       ↑

Krok 3: Porównaj z rodzicem (1)
0 < 1 → ZAMIEŃ

[0, 3, 1, 5, 4, 10, 2]
 ↑

Krok 4: Element jest korzeniem → KONIEC

5.3. Implementacja:

6. Operacja: Heapify Down (Bubble Down)

Użycie: Po usunięciu korzenia.

6.1. Idea:

1. Zamień korzeń z ostatnim elementem
2. Usuń ostatni element
3. Porównaj nowy korzeń z dziećmi
4. Zamień z mniejszym dzieckiem
5. Powtarzaj aż:
   - Element ≤ oba dzieci (OK)
   - Element jest liściem

6.2. Wizualizacja:

Min-Heap: [1, 3, 2, 5, 4, 10]
Usuń korzeń (1)

Krok 1: Zamień korzeń z ostatnim
[10, 3, 2, 5, 4, 1]
 ↑               ↑

Krok 2: Usuń ostatni
[10, 3, 2, 5, 4]
 ↑

Krok 3: Porównaj z dziećmi (3, 2)
Min(3, 2) = 2
10 > 2 → ZAMIEŃ z 2

[2, 3, 10, 5, 4]
       ↑

Krok 4: Porównaj z dziećmi (brak)
Element jest liściem → KONIEC

Wynik: [2, 3, 10, 5, 4]

6.3. Implementacja:

7. Wstawianie do kopca

Złożoność: O(log n) – wysokość drzewa

8. Usuwanie minimum (extract-min)

Złożoność: O(log n)

9. Podglądanie minimum (peek)

Złożoność: O(1) ✅

10. Budowanie kopca (heapify)

10.1. Budowanie z tablicy:

Złożoność: O(n) – nieoczywiste, ale prawda! 🎉

10.2. Dlaczego O(n)?

Analiza:
- Liście (połowa węzłów): 0 operacji
- Poziom nad liśćmi: max 1 swap każdy
- Poziom wyżej: max 2 swapy każdy
- ...
- Korzeń: max log(n) swapów

Suma: n/2*0 + n/4*1 + n/8*2 + ... = O(n)

11. Max-Heap

Max-Heap to odwrotność Min-Heap – największy element w korzeniu.

11.1. Implementacja:

12. Moduł heapq w Pythonie

Python ma wbudowany moduł heapq dla Min-Heap:

12.1. Max-Heap w heapq:

Python heapq to tylko Min-Heap. Dla Max-Heap używamy sztuczki:

13. Złożoność operacji kopca

Operacja	Złożoność	Uwagi
Insert	O(log n)	Heapify up
Extract-min	O(log n)	Heapify down
Peek (min)	O(1) ✅	Tylko odczyt korzenia
Build-heap	O(n) ✅	Z tablicy
Search	O(n) ❌	Brak uporządkowania
Delete (any)	O(n)	Musi znaleźć + heapify

Kluczowe: Peek = O(1), Insert/Extract = O(log n) ✅

14. Zastosowania kopców

14.1. Kolejka priorytetowa (Priority Queue)

14.2. Heap Sort (sortowanie przez kopcowanie)

Złożoność: O(n log n) – gwarantowane!

14.3. Znajdowanie k-tego najmniejszego/największego

14.4. Scalanie k posortowanych list

14.5. Mediana ze strumienia danych

15. Porównanie: Kopiec vs inne struktury

15.1. Kopiec vs BST:

Operacja	Kopiec (Min)	BST (zbal.)
Znajdź min	O(1) ✅	O(log n)
Extract-min	O(log n)	O(log n)
Insert	O(log n)	O(log n)
Search	O(n) ❌	O(log n) ✅
In-order	NIE	TAK ✅

Kopiec: Dla min/max i kolejki priorytetowej BST: Dla wyszukiwania i uporządkowania

15.2. Kopiec vs tablica posortowana:

Operacja	Kopiec	Tablica posort.
Znajdź min	O(1) ✅	O(1) ✅
Extract-min	O(log n) ✅	O(n) (shift)
Insert	O(log n) ✅	O(n) (shift)
Build	O(n) ✅	O(n log n)

Kopiec lepszy dla dynamicznych operacji!

16. d-ary Heap (uogólnienie)

d-ary heap: Każdy węzeł ma d dzieci (nie tylko 2).

Zastosowania: - d=3 (ternary heap) – kompromis między wysokością a liczbą porównań - d=4 (quaternary heap) – jeszcze niższa wysokość

17. Podsumowanie

Kopiec binarny (Binary Heap):

Zupełne drzewo binarne z właściwością kopca
Min-Heap: Rodzic ≤ dzieci (min w korzeniu)
Max-Heap: Rodzic ≥ dzieci (max w korzeniu)
Reprezentacja: Tablica (nie potrzeba wskaźników!)

Operacje:

Operacja	Złożoność	Uwagi
Peek	O(1) ✅	Najważniejsza zaleta!
Insert	O(log n)	Heapify up
Extract	O(log n)	Heapify down
Build	O(n) ✅	Z tablicy
Search	O(n) ❌	Brak uporządkowania

Wzory na indeksy:

Zalety: - ✅ Peek O(1) – szybki dostęp do min/max - ✅ Reprezentacja tablicowa – oszczędność pamięci - ✅ Build O(n) – efektywna budowa - ✅ Prostsza niż BST/AVL - ✅ Cache-friendly (tablica)

Wady: - ❌ Search O(n) – brak uporządkowania - ❌ Nie ma in-order – nie do sortowania dynamicznego - ❌ Delete(any) O(n) – musi znaleźć element

Zastosowania:

Kolejki priorytetowe ⭐
Scheduler w systemach operacyjnych
Algorytmy grafowe (Dijkstra, Prim)
Heap Sort – O(n log n) gwarantowane
Znajdowanie k-tego min/max
Scalanie k list
Mediana ze strumienia
Top-k problemy (np. k największych elementów)

Kiedy używać: - ✅ Potrzebujesz szybkiego dostępu do min/max O(1) - ✅ Kolejka priorytetowa - ✅ Dynamiczne wstawianie z dostępem do ekstremum - ✅ Heap Sort (in-place, O(n log n))

Kiedy NIE używać: - ❌ Potrzebujesz wyszukiwania dowolnego elementu (użyj BST) - ❌ Potrzebujesz uporządkowania wszystkich elementów (użyj BST) - ❌ Tylko statyczne dane (użyj posortowanej tablicy)

Kluczowa obserwacja:

Python heapq:

Co dalej warto poznać:

d-ary heaps – uogólnienie na d dzieci
Fibonacci Heap – lepsze amortyzowane złożoności (Dijkstra)
Binomial Heap – efektywne scalanie kopców
Leftist Heap – dla kolejek priorytetowych
Heap Sort – szczegółowa implementacja in-place