5270659534

Operacje na kopcu

procedurę insert (v : integer);	function deletemax : integer;
// Pesymistyczna złożoność czasowa Llog nj + 1.	// Pesymistyczna złożoność czasowa 2 Llog nj.
begin	begin
n :=n+l;	deletemax := a|l|;
a|n| :=v;	a111 := a|n|; n:=n-l;
upheap(n)	downheap(l)
end;	end;
procedura upheap (k : integer);	procedurę downheap (k : integer);
var 1, v : integer;	var i, j , v : integer;
begin	begin
v :=a|k|; a|0| := +oo; // dużą wartość	v := a[k|;
1:= k div 2; // warunek kopca jest zaburzony	while k < n div 2 do
// co najwyżej tylko dla v}	begin
while a 111 < v do	j := 2 * k; {j jest następnikiem k}
begin {węzeł 1 jest poprzednikiem węzła k}	if j < n then
a|k] := a|l];	'faljl <»lj + 11 then j :=j + 1;
k:=l; 1 :=l div 2	if v > a|j| then
end; o/	begin
a(k| :=v /\	a|k| :=v;
end; / n.	k = n // celem zakończenia pętli
02i \ 2/ + !	end else a|k| :=a|j|; k := j end; end;

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

Wykład 6. Strona 18.