Montón binomial sesgado

Estructura de datos para colas de prioridad

En informática , un montón binomial sesgado (o cola binomial sesgada ) es una estructura de datos para operaciones de cola de prioridad . Es una variante del montón binomial que admite operaciones de inserción de tiempo constante en el peor de los casos, en lugar de tiempo amortizado .

Motivación

Así como los montículos binomiales se basan en el sistema numérico binario , los montículos binarios sesgados se basan en el sistema numérico binario sesgado . ^[1] Los montículos binomiales ordinarios sufren de la complejidad logarítmica del peor caso para la inserción, porque una operación de acarreo puede caer en cascada, de manera análoga a la suma binaria. Los montículos binomiales sesgados se basan en el sistema numérico binario sesgado, donde el dígito n (indexado a cero) representa , en lugar de . Los dígitos son 0 o 1, excepto el dígito más bajo distinto de cero, que puede ser 2. Una ventaja de este sistema es que se necesita como máximo una operación de acarreo. Por ejemplo, 60 se representa como 11200 en binario sesgado (31 + 15 + 7 + 7), y sumar 1 produce 12000 (31 + 15 + 15). Dado que se garantiza que el siguiente dígito más alto no sea 2, se realiza un acarreo como máximo una vez. Esta analogía se aplica a la operación de inserción introduciendo enlaces ternarios (sesgados), que vinculan tres árboles entre sí. Esto permite que la operación de inserción se ejecute en tiempo constante. ${\displaystyle k}$ ${\displaystyle 2^{k+1}-1}$ ${\displaystyle 2^{k}}$

Estructura

Montón binomial sesgado que contiene los números del 1 al 19, mostrando árboles de rangos 0, 1, 2 y 3 construidos a partir de varios tipos de enlaces

Sencillo, escriba un sesgo y escriba b enlaces sesgados

Un montón binomial sesgado es un bosque de árboles binomiales sesgados , que se definen inductivamente:

• Un árbol binomial sesgado de rango 0 es un nodo singleton.
• Un árbol binomial sesgado de rango se puede construir de tres maneras: ${\displaystyle r+1}$
  • un enlace simple une dos árboles de rango, haciendo que uno sea el hijo más a la izquierda del otro; ${\displaystyle r}$
  • Un enlace oblicuo de tipo A vincula tres árboles. Dos árboles de rango se convierten en los hijos de un árbol de rango 0; ${\displaystyle r}$
  • Un enlace sesgado de tipo B vincula tres árboles. Un árbol de rango 0 y un árbol de rango se convierten en los hijos más a la izquierda de otro árbol de rango. ${\displaystyle r}$ ${\displaystyle r}$

Al realizar cualquier enlace, el árbol con la clave más pequeña siempre se convierte en la raíz. Además, imponemos la invariante de que solo puede haber un árbol de cada rango, excepto el rango más bajo que puede tener hasta dos.

El siguiente código OCaml demuestra las operaciones de vinculación:

tipo  ' un  montón  =  ' una  lista de árbol  y ' un árbol = Árbol de ' un * int * ' una lista de árbol              sea  ​​rango  ( Árbol  (_,  r ,  _))  =  rsea  ​​simple_link  ( Árbol  ( k1 ,  r ,  c1 )  como  t1 )  ( Árbol  ( k2 ,  r ,  c2 )  como  t2 )  =  si  k1  <=  k2  entonces  Árbol  ( k1 ,  r  +  1 ,  t2  ::  c1 )  de lo contrario  Árbol  ( k2 ,  r  +  1 ,  t1  ::  c2 ) sea  ​​skew_link  k1  ( Árbol  ( k2 ,  r ,  c2 )  como  t2 )  ( Árbol  ( k3 ,  r ,  c3 )  como  t3 )  =  si  k1  <=  k2  &&  k1  <=  k3  entonces  (* tipo A *)  Árbol  ( k1 ,  r  +  1 ,  [ t2 ;  t3 ])  de lo contrario  (* tipo B *)  sea  t1  =  Árbol  ( k1 ,  0 ,  [] )  en  si  k2  <=  k3  entonces  Árbol  ( k2 ,  r  +  1 ,  t1  ::  t3  ::  c2 )  de lo contrario  Árbol  ( k3 ,  r  +  1 ,  t1  ::  t2  ::  c3 )

A partir de estas propiedades, se puede deducir que la raíz de un árbol binomial de rango oblicuo tiene hasta hijos. El número de nodos en un árbol binomial de rango oblicuo también está limitado por . Dado que los árboles del mismo rango pueden tener diferentes números de nodos, puede haber más de una forma de distribuir los rangos en el montón. ${\displaystyle r}$ ${\displaystyle 2r}$ ${\displaystyle t}$ ${\displaystyle r}$ ${\displaystyle 2^{r}\leq |t|\leq 2^{r+1}-1}$

Estas construcciones pueden considerarse una generalización de los árboles binarios y binomiales. Un árbol binomial oblicuo construido utilizando únicamente enlaces simples es un árbol binomial ordinario, y el uso exclusivo de enlaces oblicuo de tipo A da como resultado un árbol binario perfectamente equilibrado.

Operaciones

Buscar-min

Busque en la lista de raíces el nodo que contiene la clave mínima. Esto lleva tiempo. ${\displaystyle O(\log n)}$

En una configuración imperativa, se puede mantener un puntero a la raíz que contenga la clave mínima, lo que permite el acceso en el tiempo. Este puntero debe actualizarse después de cada operación, lo que solo agrega una sobrecarga constante en la complejidad temporal. ${\displaystyle O(1)}$

En un entorno funcional sin acceso aleatorio a los nodos, se puede representar el montón como un árbol único con árboles binomiales sesgados como sus hijos. La raíz de este árbol es el mínimo del montón, lo que permite el acceso. Tenga en cuenta que este árbol no será necesariamente un árbol binomial sesgado en sí mismo. Las demás operaciones deben modificarse para tratar con este árbol único. Este concepto de raíz global se utiliza en las optimizaciones que se describen a continuación, aunque de forma ligeramente diferente. ${\displaystyle O(1)}$

Unir

Para fusionar dos montones binomiales sesgados, primero elimine cualquier árbol de rango duplicado en cada montón mediante la realización de enlaces simples . Luego, fusione los montones de la misma manera que los montones binomiales ordinarios, que es similar a la adición binaria. Los árboles con los mismos rangos se vinculan con un enlace simple y se pasa un árbol de "acarreo" hacia arriba si es necesario. Debido a que el rango de los árboles en cada montón ahora es único, se consideran como máximo tres árboles del mismo rango, lo que es suficiente para establecer un límite. ${\displaystyle O(\log n)}$

deje que  rec  unique  =  function  |  t1  ::  t2  ::  ts  cuando  rango  t1  =  rango  t2  ->  unique  ( simple_link  t1  t2  ::  ts )  |  ts  ->  tsdeje que  rec  merge_uniq  h1  h2  =  coincida con  h1 ,  h2  con  |  h1 ,  []  ->  h1  |  [] ,  h2  ->  h2  |  t1  ::  ts1 ,  t2  ::  ts2  ->  si  rango  t1  <  rango  t2  entonces  t1  ::  merge_uniq  ts1  h2  de lo contrario  si  rango  t1  >  rango  t2  entonces  t2  ::  merge_uniq  h1  ts2  de lo contrario  único  ( enlace_simple  t1  t2  ::  merge_uniq  ts1  ts2 ) deje que  h1 h2 se fusione  = merge_uniq ( h1 único ) ( h2 único )       

Insertar

Cree un árbol binomial sesgado de rango 0 (un nodo singleton) que contenga la clave que se insertará. A continuación, se consideran los dos árboles más pequeños del montón:

• Si ambos son de rango , entonces realice un enlace sesgado con estos dos árboles y el nodo singleton. El árbol resultante es de rango . Dado que solo puede haber habido como máximo un árbol de rango en el montón original, se conserva el invariante. ${\displaystyle r}$ ${\displaystyle r+1}$ ${\displaystyle r+1}$
• Si son de diferentes rangos, simplemente agregue el árbol de rango 0 al principio de la lista de raíces. Dado que la lista de raíces no tenía árboles de rango duplicados antes, no se viola el invariante, ya que habrá como máximo dos árboles de rango 0 después.

Como se realiza hasta un enlace, esta operación se ejecuta en el peor de los casos , mejorando el montón binomial que se basa en el análisis amortizado para su límite, con un peor caso de . ${\displaystyle O(1)}$ ${\displaystyle O(1)}$ ${\displaystyle O(\log n)}$

deje que  inserte  k  =  función  |  t2  ::  t3  ::  ts  cuando  rango  t2  =  rango  t3  ->  skew_link  k  t2  t3  ::  ts  |  ts  ->  Árbol  ( k ,  0 ,  [] )  ::  ts

Eliminar-min

Encuentre y descarte el nodo que contiene la clave mínima. Este nodo debe ser la raíz de un árbol. Divida sus hijos en dos grupos, aquellos con rango 0 y aquellos con rango > 0. Tenga en cuenta que puede haber más de dos hijos con rango 0, debido a los enlaces sesgados . Los hijos cuyo rango > 0 forman un montón binomial sesgado válido, ya que ya están ordenados y no tienen duplicados. Fusionar estos hijos en el montón lleva tiempo. Luego, vuelva a insertar cada uno de los hijos de rango 0 en el montón a un costo de cada uno. El tiempo total requerido es . ${\displaystyle O(\log n)}$ ${\displaystyle O(1)}$ ${\displaystyle O(\log n)}$

Tecla de disminución

Esta operación no se modifica con respecto a los montículos binomiales. Disminuir la clave de un nodo puede hacer que sea más pequeño que su padre. Intercámbielo repetidamente con su padre hasta que se cumpla la propiedad de montículo mínimo , a costa de una complejidad de tiempo. Esta operación requiere un puntero al nodo que contiene la clave en cuestión y es más fácil de realizar en una configuración imperativa. ${\displaystyle O(\log n)}$

Optimizaciones

Brodal y Okasaki demostraron cómo la complejidad temporal de la operación de fusión se puede reducir a , aplicando la técnica de "bootstrapping" de Buchsbaum y Tarjan . ^[2] ${\displaystyle O(1)}$

Sea el tipo de un montón binomial sesgado primitivo que contiene elementos de tipo . En lugar de la representación del bosque de árboles descrita anteriormente, mantenemos un solo árbol con una raíz global como mínimo. ${\displaystyle \alpha }$ ${\displaystyle H_{\alpha }}$

Sea el tipo de un montón binomial sesgado con raíz

${\displaystyle R_{\alpha }=\alpha \times H_{R_{\alpha }}}$,

es decir, un par que contiene un elemento de tipo y un montón primitivo de montones enraizados. ${\displaystyle \alpha }$

Finalmente, definimos el tipo de un montón bootstrap encerrando los montones enraizados en un tipo de opción :

${\displaystyle B_{\alpha }=\{\mathrm {Empty} \}+R_{\alpha }}$

que permite el montón vacío.

Las operaciones en este montón de arranque se redefinen en consecuencia. En el siguiente código de OCaml, el símbolo primo 'indica operaciones para montones de arranque.

tipo  ' a  bootstrap  =  |  Vacío  |  Raíz  de  ' a  rootedsea  ​​find_min'  ( Raíz  ( k ,  h ))  =  kdeje  que se fusionen'  bh1  bh2  =  coincida  bh1 ,  bh2  con  |  _,  Vacío  ->  bh1  |  Vacío ,  _  ->  bh2  |  Raíz  ( k1 ,  h1 ),  Raíz  ( k2 ,  h2 )  ->  si  k1  <=  k2  entonces  Raíz  ( k1 ,  inserte  bh2  h1 )  de lo contrario  Raíz  ( k2 ,  inserte  bh1  h2 )deje que  inserte'  k  h  =  fusionar'  ( Raíz ( k ,  [] ))  hdeje que  delete_min'  ( Root  ( x ,  h ))  =  deje que  Root  ( y ,  h1 )  =  find_min  h  en  deje que  h2  =  delete_min  h  en  Root  ( y ,  merge  h1  h2 )

La nueva operación de fusión utiliza únicamente operaciones de inserción en montones primitivos. Por lo tanto, se ejecuta en el tiempo. Esta técnica se puede aplicar a cualquier cola de prioridad con inserción en tiempo constante y fusión logarítmica. ${\displaystyle O(1)}$

Resumen de los tiempos de ejecución

Aquí se muestran las complejidades temporales ^[3] de varias estructuras de datos de montón. La abreviatura am. indica que la complejidad dada se amortiza, de lo contrario es una complejidad del peor caso. Para el significado de " O ( f )" y " Θ ( f )", consulte la notación Big O. Los nombres de las operaciones suponen un montón mínimo.

1. make-heap es la operación de construir un montón a partir de una secuencia de n elementos no ordenados. Se puede realizar en Θ ( n ) tiempo siempre que meld se ejecute en O (log  n ) tiempo (donde ambas complejidades se pueden amortizar). ^{[4] [5]} Otro algoritmo logra Θ ( n ) para montones binarios. ^[6]
2. Para los montículos persistentes (que no admiten la función 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 anteriores de delete-min y meld . ^[9] Aquí, hace que meld se ejecute en Θ (1) tiempo (amortizado, si el costo de insert es) mientras que delete-min aún se ejecuta en O (log  n ). Aplicado a montículos binomiales sesgados, produce colas de Brodal-Okasaki, montículos persistentes con complejidades óptimas en el peor de los casos. ^[8]
3. Límite inferior de ^[12] límite superior de ^[13] ${\displaystyle \Omega (\log \log n),}$ ${\displaystyle O(2^{2{\sqrt {\log \log n}}}).}$
4. colas de Brodal y los montículos de Fibonacci estrictos logran complejidades óptimas en el peor de los casos para los montículos. Primero se describieron como estructuras de datos imperativas. La cola de Brodal-Okasaki es una estructura de datos persistente que logra el mismo óptimo, excepto que no se admite la clave de disminución .

Referencias

1. 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
2. Buchsbaum, AL; Tarjan, RE (mayo de 1995). "Deques persistentes confluentes mediante arranque estructural de datos". Journal of Algorithms . 18 (3): 513–547. doi :10.1006/jagm.1995.1020. ISSN  0196-6774.
3. 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.
4. Sleator, Daniel Dominic ; Tarjan, Robert Endre (febrero de 1986). "Montones autoajustables". Revista SIAM de informática . 15 (1): 52–69. CiteSeerX 10.1.1.93.6678 . doi :10.1137/0215004. ISSN  0097-5397. 
5. Tarjan, Robert (1983). "3.3. Montones de izquierdas". Estructuras de datos y algoritmos de red . págs. 38-42. doi :10.1137/1.9781611970265. ISBN 978-0-89871-187-5.
6. Hayward, Ryan; McDiarmid, Colin (1991). "Análisis de caso promedio de 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 desde el original (PDF) el 2016-02-05 . Consultado el 2016-01-28 . 
7. "Pila binomial | Wiki de matemáticas y ciencias brillante". brilliant.org . Consultado el 30 de septiembre de 2019 .
8. 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
9. Okasaki, Chris (1998). "10.2. Abstracción estructural". Estructuras de datos puramente funcionales (1.ª ed.). pp. 158-162. ISBN 9780521631242.
10. Takaoka, Tadao (1999), Teoría de 2-3 montones (PDF) , pág. 12
11. Iacono, John (2000), "Límites superiores mejorados para emparejar montones", Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF) , Apuntes de clase en informática, vol. 1851, Springer-Verlag, págs. 63–77, arXiv : 1110.4428 , CiteSeerX 10.1.1.748.7812 , doi :10.1007/3-540-44985-X_5, ISBN  3-540-67690-2
12. Fredman, Michael Lawrence (julio de 1999). "Sobre la eficiencia de emparejar montones y estructuras de datos relacionadas" (PDF) . Revista de la Asociación de Maquinaria Computacional . 46 (4): 473–501. doi :10.1145/320211.320214.
13. Pettie, Seth (2005). Towards a Final Analysis of Pairing Heaps (PDF) . FOCS '05 Actas del 46.º Simposio anual IEEE sobre fundamentos de la informática. pp. 174–183. CiteSeerX 10.1.1.549.471 . doi :10.1109/SFCS.2005.75. ISBN .  0-7695-2468-0.
14. 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.
15. Fredman, Michael Lawrence ; Tarjan, Robert E. (julio de 1987). "Montones de Fibonacci y sus usos en algoritmos mejorados de optimización de redes" (PDF) . Revista de la Asociación de Maquinaria Computacional . 34 (3): 596–615. CiteSeerX 10.1.1.309.8927 . doi :10.1145/28869.28874. 
16. Brodal, Gerth Stølting ; Lagogiannis, George; Tarjan, Robert E. (2012). Montones de Fibonacci estrictos (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.
17. 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
18. 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.