Saltar al contenido principal

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 nn y mm elementos en tiempo O(log⁡(n+m))O(\log(n+m)). La siguiente tabla muestra las complejidades de cada implementación (en términos de O(⋅)O(\cdot)).

ImplementacioˊnInsertFindMinExtractMinHeapifyMergeHeapslog⁡n1log⁡nnn+mCola binomiallog⁡n1log⁡nnlog⁡(n+m)\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}