PL 
EnglishDomyślny
Українська⛰️ Kopiec binarny — kolejka priorytetowa
Wstawiaj i pobieraj wartości z binarnego kopca min przechowywanego jako tablica. Obserwuj, jak zamiany sift-up i sift-down przywracają własność kopca, przedstawioną zarówno jako drzewo, jak i jako leżąca u podstaw tablica.
O tej symulacji
Kopiec binarny to kompletne drzewo binarne — każdy poziom w pełni wypełniony poza ewentualnie ostatnim, wypełnianym od lewej do prawej — przechowywane zwięźle w zwykłej tablicy bez wskaźników. Dla dowolnego indeksu i jego rodzic znajduje się pod ⌊(i−1)/2⌋, a dzieci pod 2i+1 i 2i+2.
🔬 Co pokazuje
Kopiec min narysowany jednocześnie jako drzewo binarne i jako tablica indeksowana, z animacją zamian sift-up i sift-down przy każdej operacji.
🎮 Jak korzystać
Wstawiaj wartości pojedynczo, pobieraj minimum lub zbuduj cały kopiec naraz z losowej tablicy za pomocą algorytmu Floyda działającego w czasie O(n).
💡 Czy wiesz, że…
Zbudowanie kopca z n nieuporządkowanych wartości metodą Floyda zajmuje O(n), a nie O(n log n) — ponieważ większość węzłów leży blisko dna drzewa, gdzie operacja sift-down wykonuje niewiele pracy.
Często zadawane pytania
Dlaczego kopiec binarny można przechowywać w tablicy bez wskaźników?
Ponieważ jest to kompletne drzewo binarne, wypełniane poziom po poziomie bez luk, rodzica i dzieci węzła można obliczyć bezpośrednio z jego indeksu w tablicy (rodzic = ⌊(i−1)/2⌋, dzieci = 2i+1 i 2i+2).
Jaka jest różnica w złożoności czasowej między sift-up a sift-down?
Obie operacje działają w czasie O(log n) w najgorszym przypadku, ponieważ każda podąża tylko jedną ścieżką od korzenia do liścia o długości ⌊log₂ n⌋. Sift-up wykonuje co najwyżej jedno porównanie na poziom z rodzicem, podczas gdy sift-down wykonuje do dwóch porównań na poziom z obydwoma dziećmi.
Dlaczego budowanie kopca z n elementów zajmuje O(n), a nie O(n log n)?
Algorytm budowania kopca Floyda wywołuje sift-down tylko na węzłach wewnętrznych, zaczynając od ostatniego i pracując w górę do korzenia. Większość węzłów znajduje się blisko dna drzewa, gdzie sift-down może przemieścić się tylko na krótką odległość.
Jaka jest różnica między kopcem min a kopcem max, i jak kopiec wypada w porównaniu ze zbalansowanym BST dla kolejki priorytetowej?
Kopiec min utrzymuje najmniejszą wartość w korzeniu (rodzic ≤ dzieci); kopiec max utrzymuje największą (rodzic ≥ dzieci). W porównaniu ze zbalansowanym drzewem poszukiwań binarnych kopiec daje takie samo O(log n) wstawianie i O(log n) pobieranie minimum, ale z prostszą implementacją opartą na tablicy.