Wróćmy na chwilę do rysunku 9.3(a). Etykietami wierzchołków kopca są tam liczby naturalne od 1 do 12. Zauważmy, że przy takiej numeracji wierzchołków, synami węzła o etykiecie k są węzły o etykiecie 2k i 2k+1. Łatwo zauważyć, że nie jest to przypadek. Wyobraźmy sobie wyższe drzewo, którego wierzchołki zostały ponumerowane liczbami naturalnymi (zaczynając od 1) w porządku "wszerz". Na poziomie k-tym kopca, o ile jest całkowicie wypełniony, znajduje się 2^k elementów. Ponadto, jeśli węzeł z jakiegoś poziomu ma lewego syna, to wszystkie poprzedzające go węzły na tym poziomie, mają obu synów. Wynika stąd, że jeśli węzeł na poziomie k drzewa ma numer p, to jego lewy syn ma numer 2^k+1 + 2(p-2^k) = 2p, a prawy syn, o ile istnieje, ma numer 2p+1. Znalezienie ojca dowolnego wierzchołka też nie przedstawia problemu: jeśli numerem wierzchołka jest p, to numerem jego ojca jest p div 2. Rozważania te prowadzą do następującej prostej reprezentacji kopca.

Kopiec reprezentujemy przez obiekt typu Heap o dwóch atrybutach Tab i idx, por. rysunek 9.5(a). Tab jest tablicą wszystkich etykiet umieszczonych w kopcu, a idx jest ich liczbą. Organizacja elementów w tablicy wynika z numeracji węzłów kopca w porządku "wszerz":

Na rysunku 9.5 (b) przedstawiono tablicową reprezentację kopca, a obok drzewo-kopiec (por. rysunek 9.5.(c)). Pozycje większe od 11 są puste, gdyż kopiec ma aktualnie tylko 11 wierzchołków. Tablica jest nieco większa, tak by można było dołączyć do niej nowe elementy. J

Zgodnie z tym co było powiedziane do tej pory, przekształcenie kopca-drzewa w tablicę-kopiec polega na odczytaniu etykiet drzewa algorytmem BFS, o którym była mowa w wykładzie VII p1. i zapisaniu etykiet, kolejno odwiedzanych wierzchołków, w tablicy. Odwrotnie, utworzenie drzewa-kopca na podstawie jego tablicowej reprezentacji też nie przedstawia większych problemów. Jeżeli H jest obiektem typu Heap, tzn. tablicową reprezentacją kopca, to następująca rekurencyjna procedura rekurencyjna Buduj_Kopiec, wywołana dla parametru i=1, zwróci korzeń drzewa-kopca.

Poprawność przedstawionej procedury jest dość oczywista. Otrzymane drzewo jest częściowo uporządkowane, ponieważ z własności tablicy TAB wynika, że dla dowolnego wierzchołka v konstruowanego drzewa,

Liśćmi w tym drzewie są tylko te wierzchołki, które odpowiadają pozycjom n div2+1, n div2+2,..., n-1, n. Czytelnikowi pozostawiamy uzasadnienie, że otrzymane drzewo jest doskonałe.

Reprezentacja tablicowa kopca umożliwia bardzo łatwą implementację algorytmów wstawiania i usuwania elementu minimalnego.

Operacja insert, wstawiania elementu do kopca danego w reprezentacji tablicowej, odbywa się dokładnie tak, jak to przedstawiliśmy w punkcie drugim tego wykładu. Teraz jednak nie ma problemu znalezienia pierwszego z prawej wierzchołka wewnętrznego, do którego należy dowiązać nowy element - jest to pozycja (idx+1) div 2. Natomiast, pozycją nowego elementu jest pozycja następna po wskazywanej przez atrybut idx. Algorytm wstawiania przedstawiliśmy jako funkcję insert z dwoma parametrami: obiektem typu Heap i wstawianą etykietą.

Heap Insert (H: Heap, e: Et){
	H.idx := H.idx+1;	// zwiększamy liczbę elementów kopca
	H.TAB[k] := e; k := H.idx;	//na pierwszej wolnej pozycji w tablicy TAB umieszczamy etykietę e
	while (k>1) and (H.TAB[k]<H.TAB[k div 2]) do
	swap(H.TAB[k], H.TAB[k div 2])	// zamień etykiety ojca i syna
	k := k div 2;
	od;
	return H;
}

Niech H będzie tablicową reprezentacją kopca, por. rysunek 9.5 (b). Przypuśćmy, że chcemy dołączyć do tego kopca element 1. Działanie algorytmu insert(H,1) przedstawiono na rysunku 9.6. Po dołączeniu 1 na pierwszej wolnej pozycji w tablicy TAB, musimy sprawdzić uporządkowanie. Na rysunkach (b), (c), (d) zaznaczono pozycje, porównywane kolejno z dołączonym elementem 1. Ostatecznie tablica (d) reprezentuje kopiec z wstawionym elementem 1.

Pytanie 4: Jakie etykiety będą liśćmi, jeśli do kopca z rysunku 9.6 (d) wstawiono kolejno elementy -1, 0 ?

Operacja usuwania elementu minimalnego z kopca, w jego tablicowej reprezentacji, odbywa się dokładnie tak jak przedstawiono w punkcie 3 tego wykładu. Podobnie jak przy wstawianiu, nie ma problemu z wyszukaniem ostatniego liścia, bo jest to po prostu ostatni element tablicy reprezentującej kopiec. Algorytm usuwania delmin przedstawiliśmy jako funkcję z jednym parametrem typu Heap. Proces poprawiania ścieżki został wyróżniony i przedstawiony jako osobna procedura DownHeap, ponieważ będzie on wykorzystany również w następnym punkcie wykładu.

Heap delmin(H: Heap){
	H.TAB[1] := H.TAB[H.idx];	//zastępujemy etykietę korzenia etykietą ostatniego liścia
	H.idx := H.idx - 1;	//zmniejszamy liczbę elementów kopca
	DownHeap(H.TAB, H.idx, 1);	//poprawiamy uporządkowanie na ścieżce od korzenia
	return H;
}

Algorytm poprawiania ścieżek, DownHeap, też jest bardzo prosty: zaczynając od korzenia aktualnie rozważanego kopca, zamieniamy etykietę ojca z etykietą mniejszego z synów i kontynuujemy ten proces od zmienionej pozycji wzdłuż jednej ścieżki, w dół, do liścia. Parametrami algorytmu są: tablica zawierająca etykiety kopca, liczba elementów w tablicy i pozycja od której zaczynamy poprawiać uporządkowanie.

DownHeap (TAB: tablica, n: int, k : int){
	i, j, v : int;
	v := TAB[k];
	while (k £ n div 2) do	//Poprawianie ścieżki od v
	j := 2*k;	//TAB[j] jest etykietą lewego syna wierzchołka k-tego
	if (j < n) then	//wierzchołek na pozycji k-tej ma dwóch synów,
	if (TAB[j] >TAB[j+1]) then j := j+1 fi	//j jest pozycją mniejszego z synów
	fi;
	if (v < TAB[j]) then exit fi;	//Porównujemy etykietę mniejszego z synów z etykietą ojca
	TAB[k] := TAB[j]; k := j;	//Etykieta z pozycji j-tej wędruje "w górę drzewa" na pozycję k-tą i proces powtarzamy dla wierzchołka j
	od;
	TAB[k] := v;	// znaleźliśmy miejsce dla etykiety v.
}

Niech H będzie tablicową reprezentacją kopca, przedstawioną na rysunku 9.5 (b). Działanie algorytmu delmin(H) zilustrowano na rysunku 9.7. Ostatni element tablicy jest kandydatem na miejsce aktualnego korzenia (rysunek 9.7(a)) Teraz następuje poprawianie uporządkowania. Porównujemy mniejszego z synów korzenia z etykietą 7 (rysunek 9.7(b)). Ponieważ 7>3, więc na pozycji pierwszej pojawia się 3. Zanim wpiszemy 7 na pozycję trzecią porównujemy ją z mniejszym z synów tej pozycji, czyli z liczbą 10. Ponieważ 7<10, więc kończymy wykonanie pętli i umieszczamy ostatecznie 7 na pozycji trzeciej. Wynikiem działania algorytmu delmin(H) jest tablica 9.7(c). J

Pytanie 5: Jakie etykiety znajdą się w liściach drzewa, jeśli z kopca przedstawionego na rysunku 9.6(b) usuniemy dwukrotnie minimum?


		1	2	3	4	5	6	7	8	9	10	11	12
	TAB:	2	4	3	8	5	11	10	12	9	6	7	1
(a)							¯	___	___	___	___	___	_¯

		1	2	3	4	5	6	7	8	9	10	11	12
	TAB:	2	4	3	8	5	1	10	12	9	6	7	11
(b)				¯_	___	___	_¯

		1	2	3	4	5	6	7	8	9	10	11	12
	TAB:	2	4	1	8	5	3	10	12	9	6	7	11
(c)		¯_	___	_¯

		1	2	3	4	5	6	7	8	9	10	11	12
	TAB:	1	4	2	8	5	3	10	12	9	6	7	11
(d)													¯
													idx
								Rysunek 9.6