Kopiec — kolejka ważności

🎯 Po co Ci to?

Poprzednia jednostka skończyła się pytaniem: jak zawsze błyskawicznie wydawać najważniejszy element? Szpitalny SOR przyjmuje nie po kolei, lecz po pilności; nawigacja rozwija zawsze najbliższą trasę; system operacyjny uruchamia proces o najwyższym priorytecie. Posortowana lista jest za wolna w aktualizacji, zwykła kolejka nie zna ważności. Odpowiedzią jest kopiec — struktura pomysłowa jak niewiele innych: trzyma najważniejszy element na wyciągnięcie ręki, a przy tym pozwala tanio dokładać nowe i zdejmować mistrza. Poznasz też jego drugie życie — jako motor eleganckiego sortowania.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

• opisać kopiec przez jego niezmiennik (rodzic ważniejszy od dzieci) i dwie operacje;
• wyjaśnić, czemu operacje kopca kosztują $O(\log n)$, a odczyt maksimum $O(1)$;
• wskazać zastosowania: kolejka priorytetowa i sortowanie przez kopcowanie.

🔁 Przypomnij sobie

Z 9.3: kolejka priorytetowa potrzebuje szybkiego dostępu do najważniejszego; z 2.7/6.6: struktura drzewa o głębokości $\log n$; z 6.8: znajdowanie maksimum.

📘 Wyjaśnienie

📐 DEFINICJA — kopiec (kopiec maksymalny): drzewo binarne spełniające niezmiennik kopca: każdy węzeł jest ważniejszy (większy) lub równy swoim dzieciom. Wniosek: największy element zawsze jest w korzeniu.

Po ludzku: hierarchia, w której każdy szef jest co najmniej tak ważny jak podwładni — więc na samej górze siedzi najważniejszy. Czym NIE jest: w pełni posortowaną strukturą. Kopiec gwarantuje tylko relację rodzic–dziecko, nie porządek między rodzeństwem czy poziomami. To „częściowy porządek" — i właśnie ta oszczędność czyni go szybkim.

Kluczowa sztuczka: kopiec to drzewo, ale przechowuje się go w zwykłej tablicy — bez żadnych wskaźników. Dziecko węzła o indeksie $i$ leży na $2i+1$ i $2i+2$, rodzic — na $(i-1)/2$. Arytmetyka indeksów zastępuje strukturę drzewa (znajomy trik z 9.2: tablica udaje coś bardziej złożonego).

Dwie operacje, obie $O(\log n)$:

• Dodaj element: wstaw go na koniec tablicy, potem „wypłyń" — dopóki jesteś ważniejszy od rodzica, zamień się z nim miejscami. Element wędruje w górę co najwyżej przez wysokość drzewa — $\log n$ kroków.
• Zdejmij maksimum: weź korzeń (to odpowiedź), przenieś ostatni element na jego miejsce, potem „zatop" — dopóki masz ważniejsze dziecko, zamień się z ważniejszym z dwójki. Znów $\log n$ kroków.

Odczyt maksimum bez zdejmowania to $O(1)$ — po prostu korzeń. Porównaj z alternatywami dla kolejki priorytetowej: posortowana lista czyta maksimum w $O(1)$, ale wstawia w $O(n)$; zwykła lista wstawia w $O(1)$, ale szuka maksimum w $O(n)$. Kopiec robi oba w $O(\log n)$ — kompromis, który wygrywa, gdy i dokładasz, i zdejmujesz często (czyli w każdej prawdziwej kolejce priorytetowej). W Pythonie gotowy jest moduł heapq.

Drugie życie: sortowanie przez kopcowanie. Skoro kopiec zawsze oddaje największy element — zbuduj kopiec ze wszystkich danych, a potem zdejmuj maksima jedno po drugim: wychodzą od największego do najmniejszego, czyli posortowane. Koszt: $n$ zdjęć po $\log n$ każde = $n \log n$ — ta sama optymalna klasa, co scalanie (6.6), ale bez dodatkowej pamięci (kopiec żyje w tej samej tablicy). To trzecie sortowanie $n \log n$ w tej książce — obok scalania (gwarancja + pamięć) i szybkiego (średnia + w miejscu); kopcowanie łączy zalety obu: gwarancję najgorszego przypadku $n \log n$ i brak dodatkowej pamięci. Cena? W praktyce nieco wolniejsze od quicksorta (gorsza stała, mniej przyjazne dla pamięci podręcznej procesora) — więc bywa wybierane, gdy gwarancja jest ważniejsza niż szczytowa szybkość.

💭 Pomyśl: Kopiec trzyma największy element w korzeniu, ale NIE jest w pełni posortowany. Ile pracy kosztowałoby wypisanie wszystkich elementów po kolei (posortowanych) — i czemu to dokładnie sortowanie przez kopcowanie?

Sprawdź odpowiedź

Kopiec daje maksimum za darmo, ale drugie-co-do-wielkości może być którymkolwiek z dzieci korzenia — nie wiadomo z góry. Żeby wypisać wszystko po kolei, trzeba zdejmować maksimum $n$ razy, za każdym razem naprawiając kopiec ($\log n$) — razem $n \log n$. To jest właśnie sortowanie przez kopcowanie! Obserwacja głębsza: częściowy porządek kopca (tylko rodzic > dzieci) to dokładnie tyle struktury, ile trzeba, by tanio wydawać maksima — ani mniej (nie znałbyś największego), ani więcej (pełne sortowanie kosztowałoby tyle samo, a utrudniało wstawianie). Kopiec to mistrzostwo w „utrzymuj minimum porządku potrzebnego do zadania".

⚠️ Uwaga, pułapka

Kopiec maksymalny (korzeń = największy) i minimalny (korzeń = najmniejszy) różnią się tylko kierunkiem porównania — ale pomylenie ich to klasyczny błąd. Kolejka „najpilniejszy pierwszy" chce maksymalnego (albo minimalnego, jeśli pilność koduje mała liczba — jak „priorytet 1 = najwyższy"!). Zawsze ustal wprost: czy „najważniejszy" to największa, czy najmniejsza liczba? Nawigacja szukająca najkrótszej trasy używa kopca minimalnego (najmniejszy koszt na wierzchu) — intuicja „najważniejszy = największy" prowadzi tu na manowce.

🌍 Powiązania

Kopiec (jako kolejka priorytetowa) napędza rzeczy, których używasz codziennie nie wiedząc o tym: algorytm najkrótszej drogi Dijkstry (nawigacja rozwija zawsze najbliższy nieodwiedzony punkt — kopiec minimalny), szeregowanie procesów przez system operacyjny, kompresję Huffmana (2.6 — łączenie dwóch najrzadszych symboli, wybieranych z kopca), symulacje zdarzeń (następne zdarzenie w czasie = minimum). Gdziekolwiek trzeba wielokrotnie „wyjąć najważniejszy i dołożyć nowe" — pod spodem prawie na pewno pracuje kopiec.

🛠️ Teraz Ty

Bez komputera: zbuduj kopiec maksymalny, dodając kolejno 5, 3, 8, 1, 9, 2 (rysuj drzewo, „wypławiaj" każdy nowy element) — jaki jest korzeń? Potem zdejmij maksimum i pokaż „zatapianie". Z komputerem: użyj heapq (to kopiec minimalny — uwaga!) do zbudowania kolejki priorytetowej zgłoszeń (priorytet, opis); wypisz zgłoszenia w kolejności pilności. Bonus: zaimplementuj sortowanie przez kopcowanie i porównaj z sorted.

📐 Definicje tej lekcji

• Kopiec — drzewo binarne z niezmiennikiem „rodzic ważniejszy od dzieci"; największy w korzeniu; trzymany w tablicy (dzieci na $2i+1$, $2i+2$).
• Operacje kopca — dodaj (wypłyń) i zdejmij maksimum (zatop), obie $O(\log n$); odczyt maksimum $O(1)$.
• Sortowanie przez kopcowanie — zbuduj kopiec, zdejmuj maksima; $O(n \log n)$ w miejscu, z gwarancją.

📌 Najważniejsze w pigułce

• Kopiec to kolejka priorytetowa: najważniejszy zawsze na wierzchu, dodawanie i zdejmowanie w $O(\log n)$.
• Częściowy porządek (rodzic > dzieci) to dokładnie tyle struktury, ile trzeba — stąd szybkość.
• Kopcowanie sortuje w $n \log n$ z gwarancją i bez dodatkowej pamięci — łączy atuty scalania i szybkiego.

🎒 Zadania

1. Dodaj do pustego kopca maksymalnego kolejno: 4, 8, 2, 9, 5. Narysuj kopiec po każdym dodaniu i podaj zawartość tablicy na końcu.

Wskazówka i odpowiedź

4 → [4]. 8 (wypływa nad 4) → [8,4]. 2 → [8,4,2]. 9 (wypływa: nad 4, potem nad 8) → [9,8,2,4]. 5 (wypływa nad 4? rodzic 5 to indeks (4-1)/2=1, czyli 8 — 5<8, zostaje) → [9,8,2,4,5]. Korzeń 9 = największy ✓. Zauważ, że tablica NIE jest posortowana ([9,8,2,4,5]), a mimo to niezmiennik kopca trzyma: 9>8, 9>2, 8>4, 8>5. Tyle porządku wystarczy, by maksimum było na wierzchu.

2. Kolejka priorytetowa na zwykłej posortowanej liście: odczyt maksimum $O(1)$, ale wstawianie $O(n)$. Dla scenariusza „10 000 wstawień i 10 000 zdjęć maksimum" porównaj koszt listy i kopca.

Wskazówka i odpowiedź

Lista: wstawienia $10^4 \times O(n) \approx 10^4 \times 5000 = 5 \cdot 10^7$; zdjęcia $10^4 \times O(1)$. Razem ~$5 \cdot 10^7$. Kopiec: oba typy operacji $\times O(\log n) \approx 10^4 \times 14 \times 2 \approx 3 \cdot 10^5$. Kopiec ~150 razy szybszy — bo nie płaci $O(n)$ za żadną operację. Gdy i wstawiasz, i zdejmujesz dużo, częściowy porządek kopca bije pełny porządek listy. (Gdybyś tylko wstawiał raz i zdejmował wszystko — to zwykłe sortowanie, i tu akurat kopcowanie = lista posortowana; przewaga kopca rośnie z przeplotem operacji.)

3. Nawigacja szuka najkrótszej trasy i używa kolejki priorytetowej „najbliższy nieodwiedzony punkt pierwszy". Kopiec maksymalny czy minimalny? Co byłoby, gdybyś pomylił?

Wskazówka i odpowiedź

Minimalny — „najbliższy" to najmniejszy koszt dotarcia, więc na wierzchu chcemy minimum. Pomyłka (kopiec maksymalny) kazałaby rozwijać zawsze najdalszy punkt — algorytm błądziłby po najgorszych trasach, dając albo zły wynik, albo wieczność liczenia. To praktyczna ilustracja pułapki z ⚠️: „priorytet" trzeba przełożyć na „większa czy mniejsza liczba na wierzchu" — a przy kosztach/odległościach prawie zawsze chodzi o minimum.

🔍 Sprawdź, czy umiesz

• Sformułować niezmiennik kopca i wskazać, gdzie jest największy element.
• Wykonać dodawanie (wypływanie) i zdejmowanie maksimum (zatapianie) na kartce.
• Wyjaśnić, czemu kopiec bije posortowaną listę przy przeplocie wstawień i zdjęć.

---