KOPIEC

Wstawianie elementu.

(1) Dowiązać nowy wierzchołek x do pierwszego z lewej wierzchołka na przedostatnim poziomie drzewa, którego rząd jest <2.

(2) Nadać nowemu wierzchołkowi etykietę e.

(3) Jeżeli tak otrzymane drzewo nie jest częściowo uporządkowane, to przechodząc wzdłuż drogi od liścia x do korzenia, poprawić etykiety zamieniając etykietę ojca z etykietą syna, jeśli etykieta ojca jest większa niż etykieta syna.

Usuwanie minimum.

e -etykieta liścia x znajdującego się najbardziej na prawo na ostatnim poziomie kopca

(1) Usunąć wierzchołek x z drzewa d.

(2) Zastąpić etykietę w korzeniu drzewa przez e.

(3) Jeśli tak otrzymane drzewo nie jest kopcem, to zaczynając od korzenia i idąc w kierunku liścia, zamieniać etykietę ojca z etykietą tego z jego synów, którego etykieta ma mniejszą wartość, tak długo aż zostanie otrzymane drzewo częściowo uporządkowane.

Wysokość kopca to lg n

Koszt insert i delmin

Koszt sortowania= O(n lg n) + n* O(lg n)= O(n lg n)

Koszt tworzenia tablicowo: O(n) n-liczba elementów

Drzewa rozpinające.

BFS

Włóż do kolejki wybrany wierzchołek grafu i zamarkuj go.

Dopóki kolejka nie jest pusta

1 . Weź pierwszy element z kolejki i dopisz do kolejki wszystkie wierzchołki z nim incydentne, o ile nie były zamarkowane i zamarkuj je.

2. Wypisz krawędzie, po których przeszedłeś do nowych wierzchołków.

3. Usuń pierwszy element z kolejki.

a
a	b		f
	b		f	c		e
			f	c		e
				c		e		d
						e		d
								d
a		a			b		b			c
b		f			c		e			d

DFS

Włóż na stos wybrany wierzchołek grafu i zamarkuj go.

Dopóki stos nie jest pusty :

1 . Weź element ze szczytu stosu.
2 . Usuń ze stosu ten element.

3. Dopisz do stosu wszystkie wierzchołki z nim incydentne, których jeszcze nie zamarkowano, a dopisane wierzchołki zamarkuj.

4. Wypisz krawędzie, po których przeszedłeś do wierzchołków zamarkowanych w p.3.

		e	d
	f	c	c	c
a	b	b	b	b	b

a	a	f	f	e
b	f	c	e	d