Colas Binomiales

En esta sección veremos una nueva implementación de colas de prioridad. A diferencia de la implementación usando heaps, las colas binomiales permiten unir dos heaps de $n$ y $m$ elementos en tiempo $O(\log(n+m))$. La siguiente tabla muestra las complejidades de cada implementación (en términos de $O(\cdot)$).

$$\begin{array}{|c||c|c|c|c|c|c|} \hline \text{Implementación} & \text{Insert} & \text{FindMin} & \text{ExtractMin} & \text{Heapify} & \text{Merge} \\ \hline \hline \text{Heaps} & \log n & 1 & \log n & n & n+m \\ \hline \text{Cola binomial} & \log n & 1 & \log n & n & \log(n+m) \\ \hline \end{array}$$

📄️ EstructuraSingle Page

📄️ Suma de colasSingle Page

📄️ OperacionesSingle Page