Mówimy,że f-cja T(n) jest O(f(n)) jeżeli istnieją stałe c>0, n₀>=0 takie,że dla n>=n₀ T(n)<=c*f(n).

Mówimy,że f-cja T(n) jest Ω(f(n)) jeżeli istnieją stałe c>0, n₀>=0 takie,że dla n>=n₀ T(n)>=c*f(n).

Mówimy,że f-cja T(n) jest θ(f(n)) jeżeli zachodzi: T(n)=O(f(n)) i T(n)= Ω(f(n)),czyli istnieją stałe c₁,c₂>0 oraz n₀>=0 takie,że dla n>=n₀: c₂f(n)<=T(n)<=c₁f(n).

Kopiec Binarny-jest to drzewo binarne w którego węzłach znajdują się pewne wartości i które ma następujące własności: ●każdy poziom jest całkowicie zapełniony, prócz ostatniego.Ostatni jest wypeł. do miejsca bez luk, licząc od lewej strony. ●wartość każdego syna danego węzła jest nie większa niż wartość tego węzła (ojciec>=syn). Reprez.tablicowa-elementy kopca wpisujemy poziomami od lewej do prawej(od góry). Własności: ●jeżeli tablica jest indeksowana od 1 to lewy syn i-tego jest na poz. 2*i, a prawy 2*i+1. ●ojcowie: lewego-i/2, prawego-└i/2┘.

Wysokosc kopca-K. o n wezłach ma wysokość └lgn┘ Dowód(n-wezly,h-wys.):2^h<=n<=2^h+1-1 | 2^h<=n<2^h+1 | h<=lgn<h+1 | └lgn┘ = h.

Built-Heap-Dzięki logarytmicznej złożoności pojedynczych operacji wstawiania (rozszerzania kopca), całkowita złożoność tego etapu to O(nlog n).

HeapSort-Polega na usunięciu wierzchołka kopca, zawierającego element maksymalny, a następnie wstawieniu w jego miejsce elementu z końca kopca i odtworzenie porządku kopcowego. W zwolnione w ten sposób miejsce, zaraz za końcem zmniejszonego kopca wstawia się usunięty element maksymalny. Operacje te powtarza się aż do wyczerpania elementów w kopcu. Złożoność tej fazy to także O(nlog n) T(n)<=c*n*lgn. Czas HS jest również: Ω(nlgn) T(n)>=c₁nlgn. Czas pes.: Θ(nlgn).

Heapify-T(n)=c₁*h=θ(h), gdzie h to wys. Wykopcowywanego elementu.

Kolejki priorytetowe-KP S jest to stuktura danych, w ktorej można przechowywać zbiór elementów posiadających pewne priorytety (wart. całkowite) operacje:Maximum(S)-zwrac.elem.o największym priorytecie. Extract-Max(S)-usuwa z kolejki element o najw. prior. I zwraca jako wynik. Insert(S,x)wstawia element x o zadanym priorytecie.Elementy kolejki przechowujemy w kopcu uporządkowanym według priorytetów.KOPIEC: Maximum->Θ(1),Extr-Max,Insert->Θ(lgn).Uzasadnienie:algorytm wędruje w najgorszym razie przez całą wysokość kopca([lgn]),na każdym poziomie stała liczba operacji.

Implementacja	Maximum	Extract-Max	Insert
kopcowa	Θ(lgn)	Θ(lgn)	Θ(lgn)
tab.nieuporząd.	Θ(n)	Θ(n)	Θ(1)
list.dowiąz.nieup.	Θ(n)	Θ(n)	Θ(1)
tab.uporząd.	Θ(1)	Θ(1)	Θ(n)
list.dowiąz.uporząd.	Θ(1)	Θ(1)	Θ(n)

---