---
title: L6Z6 AISD
---

## Algorytmy i struktury danych
### Lista 6, zadanie 6

==Marek Padlewski, 299778==

:::info
Niech $h(v)$ oznacza odległość wierzchołka $v$ do najbliższego pustego wskaźnika w poddrzewie o korzeniu $v$. Rozważ możliwość wykorzystania drzew binarnych, równoważonych poprzez utrzymywanie następującego warunku:
$\forall v \quad h(lewy\ syn\ v) \geq ­ h(prawy\ syn\ v)$
do implementacji złączalnych kolejek priorytetowych.
:::

#### Idea
Kolejka priorytetowa jest strukturą przechowującą dane posiadające priorytet. Dzięki niej jesteśmy w stanie łatwo dostać się do elementu o najwyższym priorytecie. Chcemy zaimplementować tę strukturę używając kopca binarnego, pamiętając o warunku zrównoważenia drzewa podanego w treści zadania oraz tego, że żaden z synów danego wierzchołka, nie może mieć większego priorytetu niż ten wierzchołek. Taka struktura ułatwi nam łączenie kopców, a więc także łączenie kolejek priorytetowych.

Aby zaimplementować taką strukturę potrzebujemy napisać metody: `delete_min`, `insert` oraz `join`.

#### Algorytmy
Aby usunąć element minimalny z kopca (z największym priorytetem) po prostu pomijamy korzeń drzewa i łączymy ze sobą lewe oraz prawe poddrzewo. Zwracamy ten element minimalny.

function delete_min(T){
	min_elem = T.val
	join(T.left, T.right)
	return min_elem
}

Aby dodać nowy wierzchołek do kopca, możemy stworzyć nowe drzewo zawierające tylko ten wierzchołek, a następnie złączyć je z drzewem do którego chcemy ten wierzchołek wstawić.

function insert(T, v){
	T2 = drzewo zawierające tylko v
	join (T, T2)
}

Aby złączyć dwa kopce, najpierw sprawdzamy który z kopców ma element o większym priorytecie w korzeniu. Oznaczmy przez $k_1$ kopiec o większym priorytecie w korzeniu, a drugi kopiec jako $k_2$. Następnie rekurencyjnie łączymy prawe poddrzewo $k_1$ z kopcem $k_2$. Wtedy w kopcu wynikowym $k$, korzeniem jest korzeń $k_1$, lewe poddrzewo to te, które ma większą wartość $h$, a prawe poddrzewo ma mniejszą wartość $h$ (aby zachować warunek z zadania). Jeśli oznaczymy korzeń kopca wynikowego jako $w$, to obliczamy dla niego wartość $h$ inkrementując wartość $h$ prawego poddrzewa, czyli $h(w) = h(w.right)+1$.

function join(T1, T2){
	if (T1.val < T2.val){
		if (T1.left == null)
			T1.left = T2
		else if (T1.right == null)
			T1.right = T2
		else
			T1.right = join(T1.right, T2)
		
		if (T1.left.h < T1.right.h)
			swap(T1.left, T1.right)
		
		T1.h = T1.right.h + 1
		return T1
	}
	else{
		if (T2.left == null)
			T2.left = T1
		else if (T2.right == null)
			T2.right = T1
		else
			T2.right = join(T2.right, T1)
		
		if (T2.left.h < T2.right.h)
			swap(T2.left, T2.right)

		T2.h = T2.right.h + 1
		return T2
	}
}