Sortowanie przez kopcowanie (Heap Sort)

1. Czym jest kopiec (heap)?

Kopiec (heap) to specjalne drzewo binarne, które spełnia właściwość kopca:

Max-heap:

Każdy rodzic >= dzieci

       90
      /  \
    82    43
   / \    / \
  38 27  3  10

Tablica: [90, 82, 43, 38, 27, 3, 10]

Min-heap:

Każdy rodzic <= dzieci

        3
      /  \
    10    27
   / \    / \
  38 43  82 90

Tablica: [3, 10, 27, 38, 43, 82, 90]

2. Reprezentacja kopca w tablicy

Kopiec można reprezentować jako tablicę:

Indeksy:     0   1   2   3   4   5   6
Tablica:   [90, 82, 43, 38, 27, 3, 10]

         90 (0)
        /      \
      82 (1)   43 (2)
     /   \     /   \
   38(3) 27(4) 3(5) 10(6)

Relacje indeksowe:

3. Idea algorytmu Heap Sort

Zbuduj max-heap z nieposortowanej tablicy
Wielokrotnie:
Zamień korzeń (największy) z ostatnim elementem
Zmniejsz rozmiar kopca
Napraw kopiec (heapify)

Wizualizacja:

[38, 27, 43, 3, 9, 82, 10]
         ↓ BUILD MAX-HEAP
[82, 38, 43, 3, 9, 27, 10]  ← Max-heap

Krok 1: Zamień 82 ↔ 10
[10, 38, 43, 3, 9, 27 | 82]  ← 82 na końcu!
         ↓ HEAPIFY
[43, 38, 27, 3, 9, 10 | 82]

Krok 2: Zamień 43 ↔ 10
[10, 38, 27, 3, 9 | 43, 82]
         ↓ HEAPIFY
[38, 10, 27, 3, 9 | 43, 82]

... (powtarzaj)

Wynik: [3, 9, 10, 27, 38, 43, 82]

4. Implementacja heapify

Przykład działania heapify:

arr = [10, 82, 43, 38, 27, 3, 9], n=7, i=0

         10 (0)        largest = 0
        /      \
      82 (1)   43 (2)  left=1: arr[1]=82 > arr[0]=10 → largest=1
     /   \     /   \   right=2: arr[2]=43 < arr[1]=82 → largest=1
   38(3) 27(4) 3(5) 9(6)

largest != i → ZAMIANA arr[0] ↔ arr[1]

         82 (0)
        /      \
      10 (1)   43 (2)
     /   \     /   \
   38(3) 27(4) 3(5) 9(6)

Rekurencyjnie heapify(arr, 7, 1):

      10 (1)          largest = 1
     /   \            left=3: arr[3]=38 > arr[1]=10 → largest=3
   38(3) 27(4)        right=4: arr[4]=27 < arr[3]=38 → largest=3

largest != i → ZAMIANA arr[1] ↔ arr[3]

      38 (1)
     /   \
   10(3) 27(4)

Rekurencyjnie heapify(arr, 7, 3) → NIC (liść)

Wynik: [82, 38, 43, 10, 27, 3, 9]  ← Max-heap!

5. Implementacja Heap Sort

6. Wizualizacja z debugiem

Przykładowy wynik:

Start: [38, 27, 43, 3, 9, 82, 10]

=== BUDOWANIE MAX-HEAP ===
Heapify od indeksu 2
  Po heapify: [38, 27, 82, 3, 9, 43, 10]
Heapify od indeksu 1
  Po heapify: [38, 27, 82, 3, 9, 43, 10]
Heapify od indeksu 0
  Po heapify: [82, 27, 43, 3, 9, 38, 10]

Max-heap: [82, 27, 43, 3, 9, 38, 10]

=== SORTOWANIE ===
Iteracja 1:
  Zamiana: arr[0]=82 ↔ arr[6]=10
  Po zamianie: [10, 27, 43, 3, 9, 38, 82]
  Po heapify: [43, 27, 38, 3, 9, 10, 82]

...

7. Złożoność czasowa: O(n log n) ✅

Analiza:

Budowanie kopca: O(n)
  - n/2 węzłów wewnętrznych
  - Każdy heapify: O(log n)
  - Razem: O(n)  ← Matematycznie udowodnione!

Sortowanie: O(n log n)
  - n iteracji
  - Każda: heapify O(log n)
  - Razem: O(n log n)

CAŁOŚĆ: O(n) + O(n log n) = O(n log n)

Wszystkie przypadki: O(n log n)!

Najlepszy: O(n log n)
Średni: O(n log n)
Najgorszy: O(n log n)

Gwarantowana wydajność – zawsze O(n log n)!

8. Złożoność pamięciowa: O(1) ✅

Heap sort jest in-place! (Merge sort wymaga O(n) pamięci)

9. Stabilność: NIE ❌

Heap sort nie jest stabilny – może zmienić kolejność równych elementów.

Przykład:

Dlaczego? Zamiany na długim dystansie niszczą stabilność.

10. Iteracyjny heapify (unikanie rekurencji)

Zaleta: Unika przepełnienia stosu dla dużych danych.

11. Heap Sort vs Priority Queue

Heap jest podstawą dla kolejki priorytetowej:

Zastosowania: - Dijkstra (najkrótsza ścieżka) - A* (wyszukiwanie) - Scheduler zadań

12. Zastosowanie: Top K elementów

Złożoność: O(n log k) – lepsze niż pełne sortowanie O(n log n)!

13. Benchmark

Przykładowe wyniki:

n= 1000: Heap=0.0089s, Python=0.0003s
n= 5000: Heap=0.0567s, Python=0.0018s
n=10000: Heap=0.1234s, Python=0.0038s

Wniosek: Timsort (Python) szybszy w praktyce, ale heap sort ma gwarantowane O(n log n).

14. Porównanie: Heap Sort vs Quick Sort vs Merge Sort

Aspekt	Heap Sort	Quick Sort	Merge Sort
Najgorszy przypadek	O(n log n) ✅	O(n²) ❌	O(n log n) ✅
Średni przypadek	O(n log n)	O(n log n) ✅	O(n log n)
Pamięć	O(1) ✅	O(log n)	O(n) ❌
Stabilny	❌ NIE	❌ NIE	✅ TAK
In-place	✅ TAK	✅ TAK	❌ NIE
Wydajność praktyczna	Średnia	Najlepsza ✅	Dobra

Heap Sort: - Gwarantowane O(n log n) + in-place O(1) → Unikalna kombinacja! - Wolniejszy od quick sort średnio (gorsze cache locality)

15. Podsumowanie

Heap Sort:

Złożoność czasowa: O(n log n) ZAWSZE ✅
Złożoność pamięciowa: O(1) in-place ✅
Stabilny: NIE ❌
Adaptywny: NIE (zawsze O(n log n))

Zalety: - Gwarantowana wydajność O(n log n) - In-place O(1) pamięci ← Unikalne! - Przewidywalny (zawsze ten sam czas) - Brak najgorszego przypadku O(n²) (jak quick sort)

Wady: - Wolniejszy od quick sort średnio (gorsze cache locality) - Niestabilny - Nie adaptywny (zawsze O(n log n))

vs Quick Sort: - Heap: gwarantowane O(n log n), Quick: średnio O(n log n) - Heap: O(1) pamięci, Quick: O(log n) pamięci - Quick: szybszy w praktyce ✅

vs Merge Sort: - Heap: O(1) pamięci ✅, Merge: O(n) pamięci - Merge: stabilny, Heap: niestabilny - Merge: szybszy w praktyce

Kiedy używać:

✅ Gdy potrzebujesz gwarantowanej wydajności O(n log n) ✅ Gdy pamięć jest ograniczona (in-place!) ✅ Gdy nie potrzebujesz stabilności ✅ Embedded systems (przewidywalna wydajność + mało pamięci)

❌ Gdy wydajność średnia krytyczna (użyj quick sort) ❌ Gdy stabilność wymagana (użyj merge sort)