5270659535

Operacje na kopcu i sortowanie kopca
procedurę construct;	procedurę heapsort;
// Pesymistyczna złożoność czasowa O(n).	// Pesymistyczna złożoność czasowa wynosi
// Elementy listy q=|a,,...,an|	// 2 n log n + O(n) = 0(n log n).
// znajdują się w tablicy a[l..n| var i: integer;	// Tablica a[l..nj zawiera elementy // do posortowania yar m, i: integer;
begin	begin
for i := n div 2 downto 1 do downheap(i)	m := n;
end;	construct; for i := m downto 2 do a[i] := deletemax; n := m end;
Algorytm sortowania kopcowego daje się za następująco:	pisać za pomocą operacji kolejki priorytetowej
1 Buduj(q, S); //0(n)
1 for i:=1 to n-1 do UsuńMax(S); // (n-1)*0(log n) = 0(n log n)
1 dla danej listy g^a-,,...^] charakteryzuje się pesymistyczną złożonością czasową 0(n log n). 1

PODSTAWY INFORMATYKI. Adrian Horzyk, http://home.agh.edu.pl/--horzyk

Wykład 6. Strona 19.