\Section{Radix Heap}{30 ноября}{Татьяна Белова}

	\subsection{Radix Heap}

	
	Мы хотим написать кучу для реализации алгоритма Дейкстры.	
	
	Radix Heap работает за $\mathcal{O}(E + V \log k)$ при условии, что веса всех ребер от 1 до $k$.
	
	Будем хранить все расстояния в $m + 1$ бакетах, где $m = \lceil \log k \rceil$. 
	
	Зададим диапазоны $d_0 \le d_1 \le \dots \le d_m \le d_{m + 1} \le \infty$.
	Тогда в первом бакете будут храниться числа из промежутка $[d_0 \dots d_1)$, во втором -- из промежутка $[d_1 \dots d_2)$, в $i$-ом бакете хранятся числа из промежутка $[d_{i - 1} \dots d_i)$. В $(m + 1)$-ом бакете изначально будут лежать все расстояния. Внутри каждого бакета будем хранить расстояния в любом порядке. 
	
	Зададим ограничения на диапазоны $d_i$. Пусть $x_0 = 1$ и $\forall 1 \le i \le m$  $x_i = 2^{i - 1}$
	Скажем, что $\forall i$ $d_{i + 1} - d_i \le x_i$.
	
	Создадим очереди $q_0$, $q_1$, $\dots$, $q_m$, соответствующие бакетам.
	
	Изначально $d_0 = 0$, $d_1 = 1$, $d_{i + 1} - d_i = x_i$, $d_{m + 1} = \infty$, $q_0 = \{ start \}$, $q_m$ -- остальные вершины
	
	Для реализации алгоритма Дейкстры мы должны уметь делать Extract Min и Decrease Key. 
	
	\begin{itemize}

	\item {\bf EMin}
	
	Пусть $q_0$, $q_1$, $\dots$, $q_{i - 1}$ -- пустые.

	$q_i$ -- первая непустая очередь.
	
	Если $i \le 1$, то вытащим любой элемент из этой очереди -- он и будет минимальным. 
	
	Если нет, то нужно все элементы очереди раскидать по предыдущим очередям. Заметим, что $x_0 + \dots + x_{i - 1} = x_i \ge d_{i + 1} - d_i$. Это означает, что мы можем все элементы из очереди раскидать по предыдущим.
	Проставим следующие диапазоны: $d_0 = 1$, $d_1 = 2$, $d_{j + 1} - d_j = x_j$ или $d_{j + 1} = d_{i + 1}$, если $d_j + x_j > d_{i + 1}$, для всех предыдущих очередей и $d_{i + 1} = d_i$. Тогда все элементы распределились корректным образом. 
	
	Теперь мы хотим, чтобы $q_0$ оказалась непустой. 
	Пусть $a$ -- минимальный элемент в очереди. Тогда будем раскидывать элементы также, только теперь $d_0 = a$. 
	
	$q_0$ стала непустой, вытаскиваем из нее любой элемент.
	
	Первую непустую очередь мы ищем за $\mathcal{O}(\log k)$. Каждый элемент в итоге переместится в предыдущую очередь не более $\log k$ раз. Значит, всего EMin работает за $\mathcal{O}(V \log k)$.
	
	\item {\bf DecKey}
	
	Уменьшаем элемент. Пока он не соответствует диапазону текущей очереди, перемещаем его в предыдущую. Каждый элемент мы переместим не более $m = \log k$ раз, поэтому суммарно Decrease Key отработает за $\mathcal{O}(E + V \log k)$.
	
	
	\end{itemize}
	
	\subsection {Two Level Radix Heap} 
	
	$\mathcal{O}(E + V \frac{\log k}{\log \log k})$
	 
	Возьмем некоторое $t$. Разобьем весь диапазон на $\log_t k$ очередей, каждую очередь разобьем на $t$ кусков. Зададим диапазоны $d_{i + 1} - d_i \le t^i$.
	
	\begin{itemize}
	
	\item {\bf EMin}
	
	За $\mathcal{O}(\log_t k)$ найдем первую непустую очередь, за $\mathcal{O}(t)$ найдем первый ненулевой кусок в ней.
	
	Заметим, что $t^i = t^{i - 1} \cdot t$, что означает, что диапазон одного куска $i$-ой очереди равен диапазону $(i - 1)$-ой очереди. Тогда для того, что бы распределить кусок по предыдущим очередям, мы можем переместить все элементы из него в $(i - 1)$-ую очередь и поменять диапазоны.
	
	Тогда EMin работает за $\mathcal{O}(\log_t k + t)$. Суммарно за $\mathcal{O}(V \cdot (\log_t k + t))$. 

	\item {\bf DecKey}	

	Уменьшим значение элемента. Пока число не попадает в диапазон текущей очереди, будем перемещать его в предыдущую. Каждый элемент переместится не более, чем на $\log_t k$. Значит, суммарно Deckey работает за $\mathcal{O}(E + V \log_t k)$. 
	
	\end{itemize}	

	Возьмем $t = \frac{\log k}{\log \log k}$. Тогда алгоритм работает за $\mathcal{O}(E + V \frac{\log k}{\log \log k})$.
	
