2–3 montones

Para fusionar dos términos de forma${\displaystyle \mathbf {a} _{i}\mathbf {r} ^{i}}$y${\displaystyle \mathbf {a} '_{i}\mathbf {r} ^{i}}$, los árboles se reordenan en el tronco principal en función de las claves en la raíz de los árboles. Si${\displaystyle a_{i}+a'_{i}\geq r}$habrá un plazo de forma${\displaystyle (\mathbf {a} _{i}+\mathbf {a} '_{i}-\mathbf {r} )\mathbf {r} ^{i}}$y un árbol de carga${\displaystyle \mathbf {r} ^{i+1}}$De lo contrario, solo hay un árbol.${\displaystyle (\mathbf {a} _{i}+\mathbf {a} '_{i})\mathbf {r} ^{i}}$La suma de dos colas r-nomiales es similar a la suma de dos números en base 1.${\displaystyle r}$.

La inserción de una clave en una cola polinomial es como fusionar un único nodo con la etiqueta de la clave en la cola r-nomial existente, tomando como referencia el nodo que contiene la etiqueta de la clave.${\displaystyle O(r\log _{r}{n})}$tiempo.

Una operación de eliminación del mínimo se realiza encontrando el mínimo en la raíz de un árbol, por ejemplo${\displaystyle T}$y eliminándolo. La cola polinómica resultante${\displaystyle Q}$se vuelve a agregar${\displaystyle P-T}$en tiempo total${\displaystyle O(r\log _{r}{n})}$.

Inserción : Para insertar una nueva clave, fusione el montón (2,3) existente actualmente con un árbol de nodos único,${\displaystyle T(0)}$etiquetado con esta clave. Desde${\displaystyle 0\leq a_{k}\leq r-1=2}$En el polinomio extendido, podría ser necesario ajustar los árboles de acarreo que pueden ocurrir a partir de la inserción. Si un árbol${\displaystyle T(i)}$Se está insertando en un árbol.${\displaystyle \mathbf {a} _{i}T(i)}$En el nivel superior, hay tres casos, dependiendo del valor de${\displaystyle \mathbf {a} _{i}}$.

1. ${\displaystyle \mathbf {a} _{i}=0}$: no hay árbol${\displaystyle T(i)}$ya está en el montón, así que se inserta en el montón. El término${\displaystyle T(i)}$se añade a nuestro polinomio extendido.
2. ${\displaystyle \mathbf {a} _{i}=1}$: Formar un nuevo árbol${\displaystyle \mathbf {2} T(i)}$uniendo los dos árboles mediante una comparación para mantener la propiedad de ordenación del montón de las etiquetas.
3. ${\displaystyle \mathbf {a} _{i}=2}$: Un acarreo de${\displaystyle T(i+1)}$se realiza con dos comparaciones. Otra ronda de inserción se realiza con este árbol de acarreo en${\displaystyle \mathbf {a} _{i+1}T(i+1)}$en el montón.

Eliminar mínimo : Primero encuentra el mínimo escaneando las raíces de los árboles. Sea${\displaystyle \mathbf {a} _{i}T(i)}$sea ​​el árbol que contiene el elemento mínimo. Dado que este árbol existe, esto significa${\displaystyle \mathbf {a} _{i}}$era${\displaystyle \mathbf {1} }$o${\displaystyle \mathbf {2} }$Eliminar la raíz de este árbol significa eliminar la raíz de la cadena lineal.${\displaystyle \mathbf {a} _{i}}$copias de conexión de${\displaystyle T(i)}$. Las otras copias de${\displaystyle T(i)}$dar un árbol de la forma${\displaystyle \mathbf {b} _{i}T(i)}$dónde${\displaystyle \mathbf {b} _{i}=0}$si${\displaystyle \mathbf {a} _{i}=1}$o${\displaystyle \mathbf {b} _{i}=1}$si${\displaystyle \mathbf {a} _{i}=2}$.

La raíz que se eliminó era también la raíz de la primera copia de${\displaystyle T(i)}$, dando 2 o 3${\displaystyle T(i-1)}$árboles. Siguiendo este patrón, terminamos con la colección de árboles.

${\displaystyle \mathbf {b} _{j}T(0),\mathbf {b} _{j}T(1),\dots ,\mathbf {b} _{j}T(i)}$

dónde${\displaystyle \mathbf {b} _{j}}$es${\displaystyle \mathbf {1} }$o${\displaystyle \mathbf {2} }$para${\displaystyle j=0,\dots ,i-1}$y${\displaystyle \mathbf {b_{i}} }$como se especifica anteriormente.

Esta colección forma un montón${\displaystyle Q}$con luego se puede volver a fusionar con${\displaystyle P-\mathbf {a} _{i}T(i)}$para asegurar que solo se eliminara del montón el nodo mínimo. (La operación de fusión se realiza mediante múltiples inserciones, cada una de las cuales requiere como máximo 3 comparaciones).

Eliminación de un árbol : Los árboles enraizados en los troncos superiores del montón no se eliminan. Para eliminar el árbol${\displaystyle tree(v)}$de tipo${\displaystyle T(i-1)}$de un nodo${\displaystyle v}$, hay dos casos, uno donde el espacio de trabajo de${\displaystyle v}$es de talla 4, y otra donde la talla es mayor. Tenga en cuenta que${\displaystyle v}$es un nodo en un${\displaystyle i}$el tronco del montón.

En un espacio de trabajo de tamaño mayor a 4, el${\displaystyle i}$El tronco tiene 2 o 3 nodos. Si tiene 3 nodos, entonces puede tener la forma${\displaystyle (u,v,w)}$o${\displaystyle (u,w,v)}$En cualquier caso, eliminar${\displaystyle tree(v)}$y encoger el tronco. Tenga en cuenta que${\displaystyle v}$no puede ser el primer nodo en el${\displaystyle i}$el tronco ya que ese nodo estaría en el${\displaystyle i+1}$El tronco, que debe existir ya que los nodos en los troncos más superiores no se eliminan.

Si el${\displaystyle i}$El tronco es de la forma${\displaystyle (u,v)}$luego eliminar${\displaystyle tree(v)}$y dar cuenta de la pérdida de la${\displaystyle i}$el tronco moviéndose alrededor de otros árboles de tipo${\displaystyle T(i-1)}$en el espacio de trabajo.

En el caso en que el espacio de trabajo tenga un tamaño de 4, elimine${\displaystyle tree(v)}$y reorganizar los otros tres nodos de manera que dos queden debajo del nodo principal del espacio de trabajo. Esto crea un${\displaystyle i}$tronco de longitud dos (tres nodos en línea) pero causa una pérdida de un${\displaystyle (i+1)}$th tronco. Esta pérdida se soluciona moviendo árboles desde el espacio de trabajo de nodos en el${\displaystyle (i+1)}$dimensión n.º. Este proceso continúa ascendiendo en dimensión hasta que se resuelve.

Disminuir clave : asumir la clave del nodo${\displaystyle v}$de dimensión${\displaystyle i-1}$se reduce y no está en el nivel superior. Entonces${\displaystyle tree(v)}$se retira y se inserta en el${\displaystyle j}$el término en el nivel superior del montón (es decir,${\displaystyle T(j)}$en el polinomio extendido), donde${\displaystyle j=dim(v)}$. Si${\displaystyle v}$estaba en el nivel superior de su árbol, entonces la propiedad del montón no fue violada por la clave de disminución y no se requiere la tala del árbol. Sin embargo, los troncos en el tronco más alto${\displaystyle i}$Puede que sea necesario reorganizarlo.

El método potencial se puede utilizar para analizar el tiempo amortizado para realizar operaciones. Sea 3 el potencial de un tronco que consta de tres nodos, y 1 el potencial de un tronco que consta de dos nodos. Defina la función${\displaystyle S}$ser la suma de los potenciales de todos los troncos, y dejar${\displaystyle \phi =-S}$El costo real será el número de comparaciones realizadas durante la operación. Tenga en cuenta que el potencial de un montón vacío es 0.

Clave de disminución: El número de nodos en los troncos puede aumentar o disminuir durante la eliminación de un árbol, dependiendo del tamaño del espacio de trabajo. En cada caso, se puede observar el cambio en el potencial y el número de comparaciones, lo que permite calcular el costo amortizado.

Dejemos que los baúles en las cajas que van hacia abajo a la izquierda sean los${\displaystyle i}$dimensión en la que uno de ellos${\displaystyle v}$puestos. Los troncos que bajan hacia la derecha son los${\displaystyle i+1}$dimensión. La${\displaystyle i}$Los troncos se ordenan por longitud no decreciente, aunque en la práctica se ordenan por las etiquetas de sus nodos de cabecera.

En los casos en que${\displaystyle w=9,8,5}$y caso 1 de${\displaystyle w=7}$, no se necesitan comparaciones debido a la propiedad de montón y${\displaystyle \Delta \phi =-\Delta S=-(-2)}$El costo amortizado en estos casos es entonces${\displaystyle {\hat {c_{i}}}=0+\Delta \phi =2}$.

En caso 1 de${\displaystyle w=7}$y ambos casos de${\displaystyle w=6}$, como máximo se necesita 1 comparación y${\displaystyle \Delta S}$disminuye en 1, lo que hace que el costo amortizado sea 1.

En el caso final donde${\displaystyle w=4}$, como máximo se realiza una comparación y${\displaystyle \Delta S}$aumenta en 1, lo que da un costo amortizado de 0. La pérdida de la${\displaystyle i+1}$El tronco deberá repararse utilizando el espacio de trabajo superior del nodo antes de que se eliminara del tronco. El proceso de reparación finaliza en uno de los casos anteriores o si no existe un tronco superior. Dado que el costo amortizado no es negativo y solo se realiza uno de los casos con amortización positiva en este proceso, el costo amortizado total permanece constante.

Insertar Al insertar un solo nodo en uno existente${\displaystyle \mathbf {a} _{0}T(0)}$en el árbol, hay dos comparaciones y${\displaystyle \Delta S=2}$si${\displaystyle \mathbf {a} _{0}=2}$o hay una comparación con${\displaystyle \Delta S=1}$Por lo tanto, el costo amortizado es 0 durante la inserción inicial y los arrastres. El tiempo real en el peor de los casos es${\displaystyle O(\log n)}$debido a los arrastres y al número constante de comparaciones en cada ocasión.

Eliminar Min Se toma${\displaystyle O(\log n)}$tiempo para encontrar el elemento mínimo, y también${\displaystyle O(\log n)}$para separar los subárboles más pequeños, ya que hay como máximo${\displaystyle O(\log n)}$de ellos. Para fusionar los subárboles,${\displaystyle O(\log n)}$Se realizan inserciones que toman un tiempo amortizado constante cada una. El tiempo amortizado es entonces${\displaystyle O(\log n)}$y también lo es el peor de los casos.