Cola ancha

En informática , la cola de Brodal es una estructura de cola de prioridad / montículo con límites de tiempo en el peor de los casos muy bajos : $O(1)$ para inserción, find-minimum, fusionar (combinar dos colas) y decrease-key y $O(\mathrm {log} (n))$ para eliminación mínima y eliminación general. Son la primera variante de montón que logra estos límites sin recurrir a la amortización de los costos operativos. Las colas de Brodal reciben su nombre de su inventor, Gerth Stølting Brodal. ^{[ 1 ]}

Aunque tienen mejores límites asintóticos que otras estructuras de colas de prioridad, son, en palabras del propio Brodal, "bastante complicadas" y "[no] aplicables en la práctica". ^{[ 1 ]} Brodal y Okasaki describen una versión persistente ( puramente funcional ) de las colas de Brodal. ^{[ 2 ]}

Definición

Una cola de Brodal es un conjunto de dos árboles. $T_{1}$ y $T_{2}$ y 5 guías . La definición de la estructura de datos de la guía se puede encontrar en la siguiente sección. Para ambos árboles, cada nodo tiene un rango , este rango es útil para operaciones posteriores y corresponde intuitivamente al logaritmo del tamaño del subárbol con raíz en el nodo. Observamos ${\text{aridad}}_{i}(x)$ el número de hijos del nodo $x$ con rango $i$ También utilizaremos $t_{1}$ para la raíz del árbol $T_{1}$ y $t_{2}$ para la raíz del árbol $T_{2}$ En cada momento dado, cada subárbol con raíz en un nodo debe cumplir con estos 5 invariantes (que luego se llamarán ${\text{RANGO}}$ invariantes):

${\text{RANGO DE HOJAS}}$ : Si $x$ es una hoja, entonces ${\text{rank}}(x)=0$ ,
${\text{RANGO PADRE}}$ : ${\text{rank}}(x)<{\text{rank}}({\text{parent}}(x))$ ,
${\text{NEXT-RANK-ARITY}}$ : Si ${\text{rank}}(x)>0$ , entonces ${\text{arity}}_{{\text{rank}}(x)-1}(x)\geqslant 2$ ,
${\text{ARITY-BOUND}}$ : ${\text{arity}}_{i}(x)\in \{0,2,3,\dots ,7\}$ destacamos que ${\text{arity}}_{i}(x)\neq 1$ ,
${\text{RANGO RAÍZ}}$ : $T_{2}=\emptyset$ o ${\text{rank}}(t_{1})\leqslant {\text{rank}}(t_{2})$ .

Aquí ${\text{NEXT-RANK-ARITY}}$ nos garantiza que el tamaño del subárbol enraizado en un nodo es al menos exponencial al rango de ese nodo. Además, ${\text{ARITY-BOUND}}$ limita el número de hijos de cada rango para un nodo dado, esto implica que todos los nodos tienen rango y grados en $O(\log n)$ .

En una cola de Brodal, no todos los nodos tendrán un valor mayor que su padre; los nodos que incumplan esta condición se denominarán nodos violadores . Sin embargo, queremos mantener el número de nodos violadores relativamente pequeño. Para realizar un seguimiento de los nodos violadores, creamos para cada nodo dos conjuntos. $V(x)$ y $W(x)$ de nodos más grandes que $x$ Intuitivamente, $V(x)$ son los nodos más grandes de $x$ con alto rango (de tal manera que $y\in V(x)$ si ${\text{rank}}(y)\geqslant {\text{rank}}(t_{1})$ ), y $W(x)$ son los nodos con rango pequeño ( ${\text{rank}}(y)<{\text{rank}}(t_{1})$ ). Estos conjuntos se implementan utilizando listas doblemente enlazadas, lo que significa que tienen un orden . En particular, todos los nodos que violan se agregan a $V(x)$ se agregan al principio de la lista y todos los nodos que violan se agregan a $W(x)$ se insertan junto a un nodo del mismo rango. Dejamos $w_{i}(x)$ denota el número de nodos en $W(x)$ de rango $i$ El $V(x)$ y $W(x)$ Las listas cumplen con estos 5 invariantes (llamaremos las ${\text{CONJUNTOS}}$ invariantes):

${\text{NODO MÍNIMO}}$ : $t_{1}=\min(T_{1}\cup T_{2})$
${\text{VIOLACIÓN DE LA CONDICIÓN}}$ : Si $y\in V(x)\cup W(x)$ entonces $y\geqslant x$
${\text{VIOLACIÓN DE LOS PADRES}}$ : Si $y<{\text{padre}}(y)$ entonces existe un nodo $x\neq y$ de tal manera que $y\in V(x)\cup W(x)$
${\text{W-RANK-BOUND}}$ : $w_{i}(x)\leqslant 6$
${\text{V-RANK-BOUND}}$ : Al denotar $V(x)=(v_{|V(x)|},\dots,v_{2},v_{1})$ , tenemos: ${\text{rank}}(v_{i})\geqslant \left\lfloor {\frac {i-1}{\alpha }}\right\rfloor$ para una cierta constante $\alpha$ .

Dado que todos los nodos tienen rango en $O(\log n)$ el ${\text{W-RANK-BOUND}}$ y ${\text{V-RANK-BOUND}}$ , todo $V(x)$ y $W(x)$ son de tamaño $O(\log n)$ .

También tenemos algunas invariantes de las raíces de los árboles. $T_{1}$ y $T_{2}$ : $t_{1}$ y $t_{2}$ (llamado el ${\text{RAÍCES}}$ invariantes).

${\text{RAÍZ-ARIDAD}}$ : $t_{i}\in \{2,3,\dots ,7\}{\text{ para }}i\in \{0,1,\dots ,{\text{rank}}(t_{i})-1\}$ ,
${\text{V-SIZE-BOUND}}$ : $|V(x)|\leqslant \alpha {\text{ rango}}(t_{1})$ ,
${\text{W-ELEMENTS-RANK}}$ : si $y\in W(t_{1})$ , entonces ${\text{rank}}(y)<{\text{rank}}(t_{1})$ .

El ${\text{V-SIZE-BOUND}}$ invariante esencialmente nos dice que si aumentamos el rango de $t_{1}$ por uno, tenemos como máximo $\alpha$ nuevas violaciones "grandes" (aquí grande significa tener un rango alto) sin violar la ${\text{V-RANK-BOUND}}$ invariante. Por otro lado, el ${\text{W-ELEMENTS-RANK}}$ invariante nos dice que todas las violaciones en $W(x)$ son "pequeños", este invariante es verdadero según la definición de $W$ . Mantener las invariantes ${\text{W-RANK-BOUND}}$ y ${\text{RAÍZ-ARIDAD}}$ no es trivial, para mantener estos utilizaremos el ${\text{Tecla de disminución}}$ operación que se puede implementar utilizando una guía como se define en la siguiente sección. Cada vez que llamemos a la ${\text{Tecla de disminución}}$ En esta operación, esencialmente haremos lo siguiente :

Agregue la nueva infracción a $V(t_{1})$ o $W(t_{1})$ dependiendo de la gravedad de dicha infracción.
Para evitar $V(t_{1})$ $V(t_{1})$ y $W(t_{1})$ $W(t_{1})$ Para evitar que se vuelva demasiado grande, realizamos de forma incremental dos tipos de transformaciones:
1. Trasladando a los hijos de $t_{2}$ a $t_{1}$ para aumentar el rango de $t_{1}$
2. Reducir el número de infracciones en $W(t_{1})$ reemplazando dos violaciones de rango $k$ por una violación de rango $k+1$

La estructura de datos de la guía

Esta definición se basa en la definición del artículo de Brodal. ^{[ 3 ]}

Suponemos que tenemos una secuencia de variables $x_{k},\dots ,x_{1}$ y queremos asegurarnos de que $\forall i\leqslant k,x_{i}\leqslant T$ para algún umbral $T$ . La única operación permitida es ${\text{REDUCIR}}(i)$ lo cual disminuye $x_{i}$ por al menos 2 y aumenta $x_{i+1}$ por como máximo 1. Podemos suponer sin pérdida de generalidad que ${\text{REDUCIR}}(i)$ reduce $x_{i}$ por 2 y aumenta $x_{i+1}$ por 1.

Si un $x_{j}$ se incrementa en uno, el objetivo de la guía es decirnos en qué índices $i$ para solicitar ${\text{REDUCIR}}(i)$ para respetar el umbral. El guía solo está autorizado a hacer $O(1)$ llamadas a la ${\text{REDUCIR}}$ función para cada incremento.

El guía tiene acceso a otra secuencia $x'_{k},\dots ,x'_{1}$ de tal manera que $x_{i}\leqslant x'_{i}$ y $x'_{i}\in \{T-2,T-1,T\}$ . Siempre y cuando después del aumento de $x_{j}$ tenemos $x_{j}\leqslant x'_{j}$ no necesitamos pedir ayuda a nuestro guía ya que $x_{j}$ está "muy" abajo $T$ . Sin embargo, si $x_{j}=x'_{j}$ antes del aumento, entonces tenemos $x_{j}+1>x'_{j}$ después del cambio.

Para simplificar la explicación, podemos suponer que $T=2$ , de modo que $x'_{i}\in \{0,1,2\}$ . La guía creará bloques en la secuencia de $x'_{i}$ de forma $2,1,1,\dots ,1,0$ donde permitimos que no haya $1$ . La guía mantiene la invariante de que cada elemento que no está en un bloque es o bien un $1$ o un $0$ . Por ejemplo, aquí están los bloques para una secuencia de $x'_{i}$ .

${\textstyle 1,{\underline {2,1,1,0}},1,1,{\underline {2,0}},{\underline {2,0}},1,0,{\underline {2,1,0}}}$

La guía se compone de 3 matrices :

$x$ la gama de $x_{k},\dots ,x_{1}$
$x'$ la gama de $x'_{k},\dots ,x'_{1}$
$p$ una matriz de punteros donde todos los $p_{i}$ para qué $x'_{i}$ están en el mismo bloque apuntarán a la misma celda de memoria que contiene un valor. Si un $x'_{i}$ no está en un bloque, entonces $p_{i}$ apunta a una celda de memoria que contiene $\bot$ .

Con esta definición, una guía tiene dos propiedades importantes :

Para cada elemento de un bloque, podemos encontrar el elemento más a la izquierda del bloque en el tiempo $O(1)$ .
Podemos destruir un bloque a tiempo $O(1)$ asignando $\bot$ a la celda de memoria a la que apunta cada elemento del bloque.

De esta forma, el guía puede decidir qué índices utilizar. ${\text{REDUCE}}$ a tiempo $O(1)$ Aquí tienes un ejemplo :

${\begin{array}{ll}{\underline {2,1,1,0}},{\underline {2,1,1,1,0}}&\\{\underline {2,1,1,0}},{\underline {2,{\color {red}2},1,1,0}}&{\text{Increment }}x'_{i}\\{\underline {2,1,1,{\color {green}1}}},{\underline {{\color {blue}0},2,1,1,0}}&{\text{REDUCE}}\\{\underline {2,1,1,1}},{\underline {{\color {green}1},{\color {blue}0},1,1,0}}&{\text{REDUCE}}\\{\underline {2,1,1,1,1,0}},1,1,0&{\text{reestablish blocks}}\\\end{array}}$

Para restablecer los bloques, los punteros del 1 y el 0 agregados al primer bloque ahora apuntan a la misma celda que todos los demás elementos del primer bloque, y el valor de la celda del segundo bloque se cambia a $\bot$ En el ejemplo anterior, solo dos ${\text{REDUCE}}$ Se necesitaban operaciones, este es el caso para todas las instancias. Por lo tanto, la cola solo necesita $O(1)$ operaciones para restablecer la propiedad.

Funcionamiento de una cola ancha

Para implementar las diferentes operaciones de la cola de prioridad , primero necesitamos describir algunas transformaciones esenciales para los árboles.

Transformaciones

Árboles de enlace

Para enlazar árboles, necesitamos tres nodos. $x_{1},x_{2}{\text{ and }}x_{3}$ de igual rango. Podemos calcular el mínimo de estos tres nodos con dos comparaciones. Aquí asumimos que $x_{1}$ es el mínimo pero el proceso es similar para todos $x_{i}$ . Ahora podemos hacer los nodos $x_{2}$ y $x_{3}$ los dos hijos más a la izquierda de $x_{1}$ y aumentar el rango de $x_{1}$ por uno. Esto conserva todo el ${\text{RANK}}$ y ${\text{SETS}}$ invariantes.

Desvinculación de árboles

Si $x$ tiene exactamente dos o tres hijos de rango ${\text{rank}}(x)-1$ , podemos eliminar a estos hijos y $x$ obtiene el rango de su nuevo hijo mayor más uno. Desde el ${\text{ARITY-BOUND}}$ condición, sabemos que la ${\text{NEXT-RANK-ARITY}}$ El invariante se conservará. Entonces, todos los ${\text{RANK}}$ y ${\text{SETS}}$ Los invariantes siguen satisfechas. Si $x$ tiene 4 o más hijos, podemos simplemente cortar dos de ellos y todas las invariantes permanecen verdaderas. Por lo tanto, la desvinculación de un árbol de rango $k$ siempre dará como resultado dos o tres árboles de rango $k-1$ (de los 2 o 3 hijos excluidos) y un árbol adicional de rango como máximo $k$ .

Manteniendo a los hijos de una raíz

Cuando agregamos y eliminamos hijos de una raíz, queremos mantener la ${\text{ROOT-RANK}}$ invariante verdadero. Para ello, utilizamos 4 guías, dos para cada raíz. $t_{1}$ y $t_{2}$ . Tener acceso constante al tiempo del hijo de $t_{1}$ creamos una matriz extensible de punteros que tiene para cada rango $i\in \{0,\dots ,{\text{rank}}(t_{1})-1\}$ un puntero a un hijo de $t_{1}$ de rango $i$ . Un guía mantendrá la condición de que ${\text{arity}}_{i}(t_{1})\leqslant 7$ y el otro sostiene ${\text{arity}}_{i}(t_{1})\geqslant 2$ ambos para $i\in \{0,\dots ,{\text{rank}}(t_{1})-3\}$ . Los hijos de $t_{1}$ de rango ${\text{rank}}(t_{1})-1$ y ${\text{rank}}(t_{1})-2$ se tratan por separado de una manera sencilla para mantener su número entre 2 y 7. El equivalente a la $x'_{i}$ La variable en la definición de la guía tendrá los valores $\{5,6,7\}$ para la guía de límites superiores y $\{4,3,2\}$ para el límite inferior.

En este contexto, cuando agregamos un hijo de rango $i$ hasta la raíz, aumentamos $x'_{i}$ por uno, y aplicar el ${\text{REDUCE}}$ operaciones. El ${\text{RECUCE}}(i)$ La operación aquí consiste en vincular tres árboles de rango $i$ lo que crea un nuevo niño de rango $i+1$ Por lo tanto, disminuimos ${\text{arity}}_{i}(t_{1})$ por tres y aumentar ${\text{arity}}_{i+1}(t_{1})$ por uno. Si este aumento resulta en demasiados hijos de rango ${\text{rank}}(t_{1})-2$ o ${\text{rank}}(t_{1})-1$ unimos a algunos de estos hijos y posiblemente aumentamos el rango de $t_{1}$ . Si aumentamos el rango de $t_{1}$ , tenemos que aumentar la longitud del array extensible gestionado por las guías.

Cortarle la relación a un hijo $t_{1}$ es muy similar, excepto que aquí el ${\text{REDUCE}}$ Esta operación corresponde a la eliminación de enlaces en un árbol.

Para la raíz $t_{2}$ La situación es casi la misma. Sin embargo, dado que ${\text{MINIMUM-NODE}}$ nos garantiza que $t_{1}$ es el elemento mínimo, sabemos que no crearemos ninguna violación al vincular o desvincular hijos de $t_{1}$ No se puede decir lo mismo de $t_{2}$ . Vincular hijos nunca creará nuevas violaciones, pero desvincular hijos puede crear hasta tres nuevas violaciones. El árbol que queda después de una desvinculación se convierte en un hijo de $t_{1}$ si tiene un rango menor que ${\text{rank}}(t_{1})$ y de lo contrario se convierte en hijo de $t_{2}$ . Las nuevas violaciones que tienen un rango mayor que ${\text{rank}}(t_{1})$ se añaden a $V(t_{1})$ . Para mantener los invariantes en el $V(t_{1})$ conjunto (es decir ${\text{V-RANK-BOUND}}$ y ${\text{V-SIZE-BOUND}}$ ), tenemos que garantizar que el rango de $t_{1}$ se incrementará y que $\alpha$ en esos invariantes se elige suficientemente grande.

Reducción de violaciones

El objetivo de esta transformación es reducir la cantidad total de posibles violaciones, lo que significa reducir $\left|\bigcup _{x\in T_{1}\cup T_{2}}V(x)\cup W(x)\right|$ .

Suponemos que tenemos dos posibles violaciones. $x_{1}$ y $x_{2}$ de igual rango $k$ . Entonces tenemos varios casos:

Si resulta que uno de los nodos no constituye una infracción, simplemente lo eliminamos de su conjunto de infracciones correspondiente.
De lo contrario, ambos nodos son violaciones. Debido a ${\text{ARITY-BOUND}}$ ${\text{ARITY-BOUND}}$ , sabemos que ambos $x_{1}$ $x_{1}$ y $x_{2}$ $x_{2}$ tener al menos un hermano. Entonces:
1. Si $x_{1}$ y $x_{2}$ si no son hermanos, entonces podemos asumir sin perder generalidad que ${\text{parent}}(x_{1})\leqslant {\text{parent}}(x_{2})$ , entonces podemos intercambiar los subárboles enraizados en $x_{1}$ y $x_{2}$ El número de infracciones solo puede disminuir durante ese intercambio.
2. Demás, $x_{1}$ $x_{1}$ y $x_{2}$ $x_{2}$ son hermanos de un nodo que llamaremos $y$ $y$ .
  1. Si $x_{1}$ tiene más de un hermano de rango $k$ , podemos simplemente cortar $x_{1}$ y convertirlo en un nodo que no viole $t_{1}$ como se describe en la subsección anterior.
  2. Demás, $x_{1}$ $x_{1}$ y $x_{2}$ $x_{2}$ son los únicos hijos de rango $k$ $k$ de $y$ $y$ ...
    1. Si ${\text{rank}}(y)>k+1$ , podemos cortar ambos $x_{1}$ y $x_{2}$ nodos de $y$ y convertirlos en nodos que no violen $t_{1}$ como se describe en la subsección anterior
    2. Demás, ${\text{rank}}(y)=k+1$ Vamos a cortar $x_{1},x_{2}{\text{ and }}y$ , el nuevo rango de $y$ será uno más el rango de su hijo más a la izquierda, Reemplazamos $y$ por un hijo en $t_{1}$ de rango $k+1$ , que se puede cortar como se describe en la subsección anterior. Si el reemplazo de $y$ se convierte en un nodo violador de rango $k+1$ , lo añadimos a $W(t_{1})$ . Finalmente hacemos $x_{1},x_{2}{\text{ and }}y$ nuevos hijos de $t_{1}$ como se describió anteriormente.

Evitar demasiadas infracciones

Los únicos conjuntos de violaciones en los que agregaremos violaciones son $V(t_{1})$ y $W(t_{1})$ Como se describió anteriormente, los invariantes en esos conjuntos se mantienen usando guías. Cuando agregamos una violación a $W(t_{1})$ Tenemos dos casos:

Si hay exactamente 6 violaciones del rango dado y hay al menos dos nodos violadores que no son hijos de $t_{2}$ , aplicamos el ${\text{REDUCE}}$ operaciones indicadas por el guía.
Si hay más de 4 violaciones que son hijos de $t_{2}$ Hemos eliminado las infracciones adicionales y las enlazamos a continuación. $t_{1}$ . Esto elimina la violación creada por estos nodos y no afecta la guía que mantiene los hijos de $t_{2}$ .

Por cada operación de cola de prioridad que se realiza, aumentamos el rango de $t_{1}$ por al menos uno moviendo un número constante de hijos de $t_{2}$ a $t_{1}$ (siempre que $T_{2}\neq \emptyset$ ). Aumentando el rango de $t_{1}$ nos permite agregar infracciones a $V(t_{1})$ sin dejar de mantener todas nuestras invariantes. Si $T_{2}\neq \emptyset$ y ${\text{rank}}(t_{2})\leqslant {\text{rank}}(t_{1})+2$ podemos cortar los hijos más grandes de $t_{2}$ , vincularlos a $t_{1}$ y luego hacer $t_{2}$ un hijo de $t_{1}$ . Esto satisface todas las invariantes. De lo contrario, cortamos un hijo de $t_{2}$ de rango ${\text{rank}}(t_{1})+2$ , desvincule este hijo y agregue los árboles resultantes a $t_{1}$ . Si $T_{2}=\emptyset$ , sabemos que $t_{1}$ es el nodo de mayor rango, por lo tanto sabemos que no se pueden crear grandes violaciones.

Operaciones de cola de prioridad

Cola de creación

${\text{MakeQueue}}()$ simplemente devuelve un par de árboles vacíos.

FindMin

${\text{FindMin}}(Q)$ devoluciones $t_{1}$ .

Insertar

${\text{Insert}}(Q,e)$ es solo un caso especial de ${\text{Meld}}(Q_{1},Q_{2})$ dónde $Q_{2}$ es una cola que solo contiene $e$ y $Q_{1}=Q$ .

Fusión

${\text{Meld}}(Q_{1},Q_{2})$ implica cuatro árboles (dos para cada cola). El árbol con la raíz mínima se convierte en el nuevo $T_{1}$ árbol. Si este árbol es también el árbol de rango máximo, podemos agregar todos los demás árboles a continuación como se describió anteriormente. En este caso, no se crea ningún nodo violatorio, por lo que no se realiza ninguna transformación en los nodos violatorios. De lo contrario, el árbol de rango máximo se convierte en el nuevo $T_{2}$ El árbol y los demás árboles se agregan a continuación como se describe en la sección "Mantenimiento de los hijos de una raíz". Si algunos árboles tienen el mismo rango que este nuevo $T_{2}$ Podemos desvincularlos antes de agregarlos. Las infracciones creadas se manejan como se explica en la sección : "Evitar demasiadas infracciones".

DisminuirTecla

${\text{DecreaseKey}}(Q,e,e')$ reemplaza el elemento de $e$ por $e'$ (con $e'\leqslant e$ ). Si $e'<t_{1}$ , intercambiamos los dos nodos; de lo contrario, manejamos la posible nueva violación como se explica en la sección "Evitar demasiadas violaciones".

Eliminar mínimo

${\text{DeleteMin}}(Q)$ se permite tomar el peor de los casos tiempo $O(\log n)$ Primero, vaciamos completamente $T_{2}$ moviendo a todos los hijos de $t_{2}$ a $t_{1}$ luego haciendo $t_{2}$ un hijo de rango 0 de $t_{1}$ . Entonces, $t_{1}$ se elimina, esto nos deja con como máximo $O(\log n)$ árboles independientes. El nuevo mínimo se encuentra entonces observando los conjuntos violatorios de la raíz antigua y observando todas las raíces de los nuevos árboles. Si el elemento mínimo no es una raíz, podemos intercambiar una raíz de un árbol de igual rango con él. Esto crea como máximo una violación. Luego, hacemos que los árboles independientes sean hijos del nuevo elemento mínimo realizando $O(\log n)$ operaciones de vinculación y desvinculación. Esto restablece el ${\text{RANK}}$ y ${\text{ROOTS}}$ invariantes. Al fusionar los $V$ y $W$ conjuntos de la nueva raíz junto con el $V$ y $W$ conjuntos de la raíz antigua juntos, obtenemos un nuevo conjunto de violación de tamaño $O(\log n)$ . Haciendo como máximo $O(\log n)$ transformaciones que reducen la violación podemos hacer que el conjunto de violación contenga como máximo un elemento de cada rango. Este conjunto será nuestro nuevo $W$ conjunto y el nuevo $V$ El conjunto está vacío. Esto restablece el ${\text{SETS}}$ invariantes. También tenemos que inicializar una nueva guía para la nueva raíz. $t_{1}$ .

Borrar

Aquí, $-\infty$ denota el elemento más pequeño posible. ${\text{Delete}}(Q,e)$ puede implementarse simplemente llamando ${\text{DecreaseKey}}(Q,e,-\infty )$ seguido de ${\text{DeleteMin}}(Q)$ .

Detalles de implementación

En esta sección, resumimos algunos detalles de implementación de la estructura de datos de cola de Brodal.

En cada árbol, cada nodo es un registro que tiene los siguientes campos:

El elemento asociado al nodo (su valor),
El rango del nodo,
punteros a los hermanos izquierdo y derecho del nodo,
un puntero al nodo padre,
un puntero al hijo de más a la izquierda,
punteros al primer elemento del nodo $V$ y $W$ conjuntos,
Punteros al elemento siguiente y anterior en el conjunto de violaciones al que pertenece el nodo. Si este nodo es el primer nodo del conjunto de violaciones $V(x)$ o $W(x)$ pertenece a, el puntero anterior apunta a $x$ .
una serie de indicadores para los hijos de $t_{1}$ de rango $i$ (con $i\in \{0,\dots ,{\text{rank}}(t_{1})-1\}$ ),
una matriz similar para $t_{2}$ ,
una matriz de punteros a nodos en $W(t_{1})$ de rango $i$ (con $i\in \{0,\dots ,{\text{rank}}(t_{1})-1\}$ ).

Finalmente, tenemos 5 guías: tres para mantener los límites superiores en ${\text{arity}}_{i}(t_{1})$ , ${\text{arity}}_{i}(t_{2})$ y $w_{i}(t_{1})$ y dos para mantener los límites inferiores en ${\text{arity}}_{i}(t_{1})$ y ${\text{arity}}_{i}(t_{2})$ .

Debido a la gran cantidad de punteros y conjuntos que debe gestionar, la cola de Brodal es extremadamente difícil de implementar. Por esta razón, se describe mejor como un objeto puramente teórico para reducir la complejidad temporal de algoritmos como el de Dijkstra . Sin embargo, la cola de Brodal se ha implementado en Scala (el repositorio de GitHub se puede encontrar aquí: https://github.com/ruippeixotog/functional-brodal-queues ). En su artículo, Gerth Stølting Brodal menciona que: "Un aspecto importante para futuros trabajos es simplificar la construcción para que sea aplicable en la práctica". ^{[ 3 ]}

Resumen de los tiempos de carrera

Aquí se muestran las complejidades temporales ^{[ 4 ]} de diversas estructuras de datos de montículo. La abreviatura am. indica que la complejidad dada está amortizada; de lo contrario, se trata de la complejidad en el peor de los casos. Para conocer el significado de " O ( f )" y " Θ ( f )", consulte la notación Big O. Los nombres de las operaciones presuponen un montículo mínimo.

↑ make-heap es la operación de construir un montón a partir de una secuencia de n elementos no ordenados. Se puede realizar entiempo Θ ( n ) siempre que meld se ejecute en tiempo O (log n ) (donde ambas complejidades se pueden amortizar).^[⁵^]^[⁶^] Otro algoritmo alcanza Θ ( n ) para montones binarios.^[⁷^]
1 2 3 Paramontículos persistentes (que no admiten decrease-key ), una transformación genérica reduce el costo de meld al de insert , mientras que el nuevo costo de delete-min es la suma de los costos antiguos de delete-min y meld .^{[ 10 ]} Aquí, hace que meld se ejecute en tiempo Θ (1) (amortizado, si el costo de insert lo es) mientras que delete-min todavía se ejecuta en O (log n ). Aplicado a montículos binomiales asimétricos, produce colas de Brodal-Okasaki, montículos persistentes con complejidades óptimas en el peor de los casos.^[⁹^]
↑ Límite inferior de $\Omega (\log \log n),$ ^{[ 13 ]} límite superior de $O(2^{2{\sqrt {\log \log n}}}).$ ^{[ 14 ]}
Las colas de Brodal y los montículos de Fibonacci estrictos alcanzan complejidades óptimas en el peor de los casos para los montículos. Inicialmente se describieron como estructuras de datos imperativas. La cola de Brodal-Okasaki es una estructura de datos persistente que alcanza el mismo óptimo, excepto queno admite la decreción de clave .

Gerth Stølting Brodal

Gerth Stølting Brodal es profesor de la Universidad de Aarhus , Dinamarca . ^{[ 20 ]} Es mejor conocido por la cola de Brodal.

Referencias

1 2 Gerth Stølting Brodal (1996). Colas de prioridad eficientes en el peor de los casos. Actas del 7.º Simposio ACM-SIAM sobre Algoritmos Discretos, págs. 52-58
↑ Gerth Stølting Brodal y Chris Okasaki (1996). Colas de prioridad puramente funcionales óptimas . Journal of Functional Programming.
^ Brodal , Gerth Stølting (1996). "Colas de prioridad eficientes en el peor de los casos" (PDF) .{{cite web}}: CS1 mantenimiento: estado de la URL ( enlace )
1 2 3 4 Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L. (1990). Introducción a los algoritmos (1ª ed.). MIT Press y McGraw-Hill. ISBN 0-262-03141-8.
1 2 3 Sleator, Daniel Dominic ; Tarjan, Robert Endre (febrero de 1986). "Montículos autoajustables" . SIAM Journal on Computing . 15 (1): 52– 69. CiteSeerX 10.1.1.93.6678 . doi : 10.1137/0215004 . ISSN 0097-5397 .
1 2 Tarjan, Robert (1983). "3.3. Montones izquierdistas". Estructuras de datos y algoritmos de red . págs. 38–42 . doi : 10.1137/1.9781611970265 . ISBN 978-0-89871-187-5.
↑ Hayward, Ryan; McDiarmid, Colin (1991). "Análisis del caso promedio de la construcción de montículos mediante inserción repetida" (PDF) . J. Algorithms . 12 : 126–153 . CiteSeerX 10.1.1.353.7888 . doi : 10.1016/0196-6774(91)90027-v . Archivado del original (PDF) el 5 de febrero de 2016. Recuperado el 28 de enero de 2016 .
↑ "Montículo binomial | Brilliant Math & Science Wiki" . brilliant.org . Consultado el 30 de septiembre de 2019 .
1 2 Brodal, Gerth Stølting; Okasaki, Chris (noviembre de 1996), "Colas de prioridad puramente funcionales óptimas", Journal of Functional Programming , 6 (6): 839– 857, doi : 10.1017/s095679680000201x
↑ Okasaki, Chris (1998). "10.2. Abstracción estructural". Estructuras de datos puramente funcionales (1.ª ed.). págs. 158–162 . ISBN 9780521631242.
↑ Takaoka, Tadao (1999), Teoría de los montículos 2-3 (PDF) , pág. 12
↑ Iacono, John (2000), "Improved upper bounds for pairing heaps", Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF) , Lecture Notes in Computer Science, vol. 1851, Springer-Verlag, pp. 63–77 , arXiv : 1110.4428 , CiteSeerX 10.1.1.748.7812 , doi : 10.1007/3-540-44985-X_5 , ISBN 3-540-67690-2
↑ Fredman, Michael Lawrence (julio de 1999). "Sobre la eficiencia de los montículos de emparejamiento y estructuras de datos relacionadas" (PDF) . Journal of the Association for Computing Machinery . 46 (4): 473– 501. doi : 10.1145/320211.320214 .
↑ Pettie, Seth (2005). Hacia un análisis final de los montículos de emparejamiento (PDF) . Actas de FOCS '05 del 46.º Simposio Anual IEEE sobre Fundamentos de la Informática. págs. 174–183 . CiteSeerX 10.1.1.549.471 . doi : 10.1109/SFCS.2005.75 . ISBN 0-7695-2468-0.
↑ Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (noviembre de 2011). "Montones de emparejamiento de rangos" (PDF) . SIAM J. Informática . 40 (6): 1463–1485.doi : 10.1137 / 100785351 .
↑ Fredman, Michael Lawrence ; Tarjan, Robert E. (julio de 1987). "Montículos de Fibonacci y sus usos en algoritmos mejorados de optimización de redes" (PDF) . Journal of the Association for Computing Machinery . 34 (3): 596– 615. CiteSeerX 10.1.1.309.8927 . doi : 10.1145/28869.28874 .
↑ Brodal, Gerth Stølting ; Lagogiannis, George; Tarjan, Robert E. (2012). Montículos estrictos de Fibonacci (PDF) . Actas del 44.º simposio sobre Teoría de la Computación - STOC '12. págs. 1177–1184 . CiteSeerX 10.1.1.233.1740 . doi : 10.1145/2213977.2214082 . ISBN 978-1-4503-1245-5.
↑ Brodal, Gerth S. ( 1996), "Colas de prioridad eficientes en el peor de los casos" (PDF) , Actas del 7.º Simposio Anual ACM-SIAM sobre Algoritmos Discretos , págs. 52–58
↑ Goodrich, Michael T .; Tamassia, Roberto (2004). "7.3.6. Construcción de montículos ascendentes". Estructuras de datos y algoritmos en Java (3.ª ed.). págs. 338–341 . ISBN 0-471-46983-1.
↑ «Sitio web de Gerth Stølting Brodal, en la Universidad de Aarhus» . Consultado el 18 de febrero de 2016 .

[8] make-heap es la operación de construir un montón a partir de una secuencia de n elementos no ordenados. Se puede realizar entiempo Θ ( n ) siempre que meld se ejecute en tiempo O (log n ) (donde ambas complejidades se pueden amortizar).^[⁵^]^[⁶^] Otro algoritmo alcanza Θ ( n ) para montones binarios.^[⁷^]

[bootstrap-meld-10] 1 2 3 Paramontículos persistentes (que no admiten decrease-key ), una transformación genérica reduce el costo de meld al de insert , mientras que el nuevo costo de delete-min es la suma de los costos antiguos de delete-min y meld .^{[ 10 ]} Aquí, hace que meld se ejecute en tiempo Θ (1) (amortizado, si el costo de insert lo es) mientras que delete-min todavía se ejecuta en O (log n ). Aplicado a montículos binomiales asimétricos, produce colas de Brodal-Okasaki, montículos persistentes con complejidades óptimas en el peor de los casos.^[⁹^]

[pairingdecreasekey-17] Límite inferior de $\Omega (\log \log n),$ ^{[ 13 ]} límite superior de $O(2^{2{\sqrt {\log \log n}}}).$ ^{[ 14 ]}

[optimum-21] Las colas de Brodal y los montículos de Fibonacci estrictos alcanzan complejidades óptimas en el peor de los casos para los montículos. Inicialmente se describieron como estructuras de datos imperativas. La cola de Brodal-Okasaki es una estructura de datos persistente que alcanza el mismo óptimo, excepto queno admite la decreción de clave .

[Brodal-1] 1 2 Gerth Stølting Brodal (1996). Colas de prioridad eficientes en el peor de los casos. Actas del 7.º Simposio ACM-SIAM sobre Algoritmos Discretos, págs. 52-58

[BrodalOkasaki-2] Gerth Stølting Brodal y Chris Okasaki (1996). Colas de prioridad puramente funcionales óptimas . Journal of Functional Programming.

[:0-3] Brodal , Gerth Stølting (1996). "Colas de prioridad eficientes en el peor de los casos" (PDF) .{{cite web}}: CS1 mantenimiento: estado de la URL ( enlace )

[CLRS-4] 1 2 3 4 Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L. (1990). Introducción a los algoritmos (1ª ed.). MIT Press y McGraw-Hill. ISBN 0-262-03141-8.

[sleator-tarjan-skew-5] 1 2 3 Sleator, Daniel Dominic ; Tarjan, Robert Endre (febrero de 1986). "Montículos autoajustables" . SIAM Journal on Computing . 15 (1): 52– 69. CiteSeerX 10.1.1.93.6678 . doi : 10.1137/0215004 . ISSN 0097-5397 .

[tarjan-leftist-6] 1 2 Tarjan, Robert (1983). "3.3. Montones izquierdistas". Estructuras de datos y algoritmos de red . págs. 38–42 . doi : 10.1137/1.9781611970265 . ISBN 978-0-89871-187-5.

[hayward-mcdiarmid-heap-build-7] Hayward, Ryan; McDiarmid, Colin (1991). "Análisis del caso promedio de la construcción de montículos mediante inserción repetida" (PDF) . J. Algorithms . 12 : 126–153 . CiteSeerX 10.1.1.353.7888 . doi : 10.1016/0196-6774(91)90027-v . Archivado del original (PDF) el 5 de febrero de 2016. Recuperado el 28 de enero de 2016 .

[9] "Montículo binomial | Brilliant Math & Science Wiki" . brilliant.org . Consultado el 30 de septiembre de 2019 .

[brodal-okasaki-11] 1 2 Brodal, Gerth Stølting; Okasaki, Chris (noviembre de 1996), "Colas de prioridad puramente funcionales óptimas", Journal of Functional Programming , 6 (6): 839– 857, doi : 10.1017/s095679680000201x

[12] Okasaki, Chris (1998). "10.2. Abstracción estructural". Estructuras de datos puramente funcionales (1.ª ed.). págs. 158–162 . ISBN 9780521631242.

[13] Takaoka, Tadao (1999), Teoría de los montículos 2-3 (PDF) , pág. 12

[Iacono-14] Iacono, John (2000), "Improved upper bounds for pairing heaps", Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF) , Lecture Notes in Computer Science, vol. 1851, Springer-Verlag, pp. 63–77 , arXiv : 1110.4428 , CiteSeerX 10.1.1.748.7812 , doi : 10.1007/3-540-44985-X_5 , ISBN 3-540-67690-2

[Fredman1999-15] Fredman, Michael Lawrence (julio de 1999). "Sobre la eficiencia de los montículos de emparejamiento y estructuras de datos relacionadas" (PDF) . Journal of the Association for Computing Machinery . 46 (4): 473– 501. doi : 10.1145/320211.320214 .

[16] Pettie, Seth (2005). Hacia un análisis final de los montículos de emparejamiento (PDF) . Actas de FOCS '05 del 46.º Simposio Anual IEEE sobre Fundamentos de la Informática. págs. 174–183 . CiteSeerX 10.1.1.549.471 . doi : 10.1109/SFCS.2005.75 . ISBN 0-7695-2468-0.

[18] Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (noviembre de 2011). "Montones de emparejamiento de rangos" (PDF) . SIAM J. Informática . 40 (6): 1463–1485.doi : 10.1137 / 100785351 .

[Fredman_And_Tarjan-19] Fredman, Michael Lawrence ; Tarjan, Robert E. (julio de 1987). "Montículos de Fibonacci y sus usos en algoritmos mejorados de optimización de redes" (PDF) . Journal of the Association for Computing Machinery . 34 (3): 596– 615. CiteSeerX 10.1.1.309.8927 . doi : 10.1145/28869.28874 .

[20] Brodal, Gerth Stølting ; Lagogiannis, George; Tarjan, Robert E. (2012). Montículos estrictos de Fibonacci (PDF) . Actas del 44.º simposio sobre Teoría de la Computación - STOC '12. págs. 1177–1184 . CiteSeerX 10.1.1.233.1740 . doi : 10.1145/2213977.2214082 . ISBN 978-1-4503-1245-5.

[22] Brodal, Gerth S. ( 1996), "Colas de prioridad eficientes en el peor de los casos" (PDF) , Actas del 7.º Simposio Anual ACM-SIAM sobre Algoritmos Discretos , págs. 52–58

[23] Goodrich, Michael T .; Tamassia, Roberto (2004). "7.3.6. Construcción de montículos ascendentes". Estructuras de datos y algoritmos en Java (3.ª ed.). págs. 338–341 . ISBN 0-471-46983-1.

[24] «Sitio web de Gerth Stølting Brodal, en la Universidad de Aarhus» . Consultado el 18 de febrero de 2016 .

[ 1 ]

[ 2 ]

[ 4 ]

[

[

[

[ 10 ]

[

[ 13 ]

[ 14 ]

[ 20 ]