Jako przykład zastosowań omawianych struktur danych, rozważmy algorytm Turniej, o którym była mowa w wykładzie III, p.5. Przypomnijmy, że problem polegał na znalezieniu elementu drugiego co do wielkości w danym ciągu składającym się z n różnych elementów. Metoda rozwiązania polegała na zbudowaniu drzewa turnieju i odszukania w nim elementów, które przegrały z elementem największym, gdyż to właśnie wśród tych elementów znajduje się element drugi co do wielkości. Trudność z implementacją tablicową polegała na zapamiętaniu, które elementy były porównywane z elementem największym, zanim jeszcze ten największy był znaleziony.

W implementacji, którą omówimy w tym punkcie, informacje o elementach danego ciągu będziemy przechowywali w specjalnie zorganizowanych listach. Każde ogniwo listy ma trzy atrybuty:

Ogniwa stosu mają atrybuty val i prev, tak jak to było przedstawione w punkcie pierwszym tego wykładu.

Rozważmy przykład III, 5.1. Niech dany będzie ciąg 6, 4, 9, 8, 5, 7, 3, 1. Na rysunku 6.10 przedstawiono kolejne stany struktury danych, użytej w omawianej implementacji algorytmu Turniej.

Strzałki poziome odpowiadają atrybutowi next w ogniwach listy. Czarne strzałki pionowe wskazują szczyt stosu elementów "pokonanych" w poprzednich rundach, a zielone, pionowe strzałki - kolejne jego ogniwa. Zauważmy, że elementy, które przegrały z elementem przegrywającym, w aktualnym porównaniu, nie są interesujące z punktu widzenia problemu wyszukiwania elementu drugiego co do wielkości. Żaden z nich na pewno nie będzie drugim co do wielkości elementem w danym ciągu. Jeżeli porównujemy dwa kolejne elementy listy x i y, to w przypadku, gdy x.val > y.val wystarczy dołączyć nowy element y.val do stosu x.stack i pominąć następne ogniwo w aktualnej liście (tzn. ominąć element y). Łatwo to zrobić wykonując następujące instrukcje:

Ponieważ w pierwszej rundzie 6 "gra" z 4, zatem cztery "przegrywa i zostaje umieszczone na stosie elementów przerywających z szóstką. Natomiast, elementem następnym po 6 będzie teraz 9, jako że dziewiątka była następnym po czwórce elementem listy. W następnym kroku tej samej rundy, 9 "gra" z 8, zatem osiem "przegrywa" i zostaje umieszczone na stosie elementów przegrywających z dziewiątką, itd. J

Zakładamy dla uproszczenia, że n, długość danego ciągu, jest potęgą dwójki, oraz n>1. Nie jest to istotne założenie z punktu widzenia algorytmu, ale pozwala uprościć kod. Zakładamy ponadto, że elementy ciągu tworzą listę, a jej początkowe ogniwo jest wartością zmiennej L.

Turniej	{
	while (L.next ¹ null) do	1	//dla dowolnej rundy
	x := L;	2
	while (x ¹ null ) do	3	//dla dowolnego meczu
	y := x.next;	4
	if x.val > y.val then	5
	x.stack := push(x.stack, y.val);	6	//dopisanie przegrywającego do stosu x'a
	else	7
	y.stack := push(y.stack, x.val);	8	//dopisanie przegrywającego do stosu x'a
	x.val := y.val;	9	//umieszczenie atrybutów wygrywającego w obiekcie x
	x.stack := y.stack	10
	fi;	11
	x. next := y .next;	12	//ominięcie jednego ogniwa listy
	x := x.next;	13	// pierwszy element następnej pary
	od	14
	od;	15
	z:= L.stack;	16	//Przeszukanie stosu zwycięzcy
	drugi := top(z); z:= pop(z);	17
		18
	while not empty(z) do	19	//wyszukiwanie elementu największego na stosie x.stack
	if top(z) > drugi then drugi := top(z) fi;	20
	z := pop(z);	21
	od;	22
	result := drugi;	23
}		24

Kolejne dwa porównywane elementy są wartościami wskazanymi przez zmienne x i y. Dla wygody, parametry elementu większego są umieszczane zawsze na zmiennej x, nawet, jeśli w aktualnym porównaniu "wygrało" y (linie 9,10: x.val := y.val; x.stack := y.stack). Pozwoli to w jednorodny i prosty sposób pominąć jeden element listy (linia 12: x.next := y.next).

Dla każdego obiektu "z" znajdującego się na aktualnej liście wskazywanej przez L, z.stack zawiera wszystkie elementy, które są mniejsze od z.val i które były bezpośrednio porównywane z z.val. Ponieważ w każdym przebiegu pętli wewnętrznej, połowa elementów zostaje odłączona od listy głównej, to po skończonej liczbie kroków pozostanie na liście tylko jeden element. Spełniony jest wtedy warunek (L.next = null) i wyjdziemy z pętli głównej. Wartość L.val jest największym elementem danego ciągu e₁,...,e_n.

Ponieważ nadal jest spełniony niezmiennik, więc poszukiwany, drugi co do wielkości element, znajduje się na stosie L.stack. Na mocy założenia (n>1) musiała zostać rozegrana chociaż jedna runda. Wynika stąd, że stos zwycięzcy L.stack nie jest pusty. W drugiej części algorytmu (linie 17-22) przeglądamy kolejno elementy tego stosu w poszukiwaniu elementu największego.

Pytanie 7: Jeżeli początkowa liczba elementów na liście wynosi 64, to jaka jest maksymalna wysokość stosów w algorytmie Turniej?