Montón sesgado

Un montón sesgado (o montón autoajustable ) es una estructura de datos de montón implementada como un árbol binario . Los montones sesgados son ventajosos debido a su capacidad para fusionarse más rápidamente que los montones binarios. A diferencia de los montones binarios , no hay restricciones estructurales, por lo que no hay garantía de que la altura del árbol sea logarítmica. Solo se deben cumplir dos condiciones:

• Se debe hacer cumplir la orden general del montón
• Cada operación (agregar, eliminar_min, fusionar) en dos montones sesgados debe realizarse utilizando una combinación especial de montones sesgados .

Un montón sesgado es una forma autoajustable de un montón izquierdista que intenta mantener el equilibrio intercambiando incondicionalmente todos los nodos en la ruta de fusión al fusionar dos montones. (La operación de combinación también se usa al agregar y eliminar valores). Sin restricciones estructurales, puede parecer que un montón sesgado sería terriblemente ineficaz. Sin embargo, el análisis de complejidad amortizada se puede utilizar para demostrar que todas las operaciones en un montón sesgado se pueden realizar en O (log n ). ^[1] De hecho, al denotar la proporción áurea , se sabe que la complejidad amortizada exacta es log _φ n (aproximadamente 1,44 log ₂ n ). ^{[2] [3]}${\textstyle \varphi ={\frac {1+{\sqrt {5}}}{2}}}$

Definición

Los montones sesgados se pueden describir con la siguiente definición recursiva : ^{[ cita requerida ]}

• Un montón con un solo elemento es un montón sesgado.
• El resultado de sesgar fusionando dos montones de sesgos y también es un montón de sesgos.${\displaystyle sh_{1}}$${\displaystyle sh_{2}}$

Operaciones

Fusionando dos montones

Cuando se van a fusionar dos montones sesgados, podemos usar un proceso similar al de la fusión de dos montones de izquierda :

• Compare las raíces de dos montones; sea p el montón con la raíz más pequeña y q el otro montón. Sea r el nombre del nuevo montón resultante.
• Sea la raíz de r la raíz de p (la raíz más pequeña) y el subárbol derecho de r sea el subárbol izquierdo de p.
• Ahora, calcule el subárbol izquierdo de r fusionando recursivamente el subárbol derecho de p con q.

plantilla < clase  T , clase CompareFunction >  SkewNode < T > * CSkewHeap < T , CompareFunction > :: _Merge ( SkewNode < T > * root_1 , SkewNode < T > * root_2 )     { SkewNode < T > * firstRoot = root_1 ;    SkewNode < T > * secondRoot = root_2 ;    si ( firstRoot == NULL )    return secondRoot ;  else if ( secondRoot == NULL )     return firstRoot ;  if ( sh_compare -> Less ( firstRoot -> clave , secondRoot -> clave ))   { SkewNode < T > * tempHeap = firstRoot -> rightNode ;    firstRoot -> rightNode = firstRoot -> leftNode ;   firstRoot -> leftNode = _Merge ( secondRoot , tempHeap );    return firstRoot ;  } demás return _Merge ( secondRoot , firstRoot );  }

Antes:

después

Fusión no recursiva

Alternativamente, existe un enfoque no recursivo que es más prolijo y requiere alguna clasificación desde el principio.

• Divida cada montón en subárboles cortando cada camino. (Desde el nodo raíz, separe el nodo derecho y haga que el hijo derecho sea su propio subárbol). Esto dará como resultado un conjunto de árboles en el que la raíz solo tiene un hijo izquierdo o no tiene ningún hijo.
• Ordene los subárboles en orden ascendente según el valor del nodo raíz de cada subárbol.
• Si bien todavía hay varios subárboles, recombine iterativamente los dos últimos (de derecha a izquierda).
  • Si la raíz del penúltimo subárbol tiene un hijo izquierdo, cámbielo para que sea el hijo derecho.
  • Vincule la raíz del último subárbol como hijo izquierdo del penúltimo subárbol.

Añadiendo valores

Agregar un valor a un montón sesgado es como fusionar un árbol con un nodo junto con el árbol original.

Eliminando valores

La eliminación del primer valor de un montón se puede lograr eliminando la raíz y fusionando sus subárboles secundarios.

Implementación

En muchos lenguajes funcionales, los montones de sesgos se vuelven extremadamente simples de implementar. Aquí hay una implementación de muestra completa en Haskell.

datos  SkewHeap  a  =  Vacío  |  Nodo  a  ( SkewHeap  a )  ( SkewHeap  a )singleton  ::  Ord  a  =>  a  ->  SkewHeap  a singleton  x  =  Nodo  x  Vacío  VacíoUnión  ::  Ord  un  =>  SkewHeap  un  ->  SkewHeap  un  ->  SkewHeap  un vacío  ` unión `  t2  =  t2 t1  ` unión `  Vaciar  =  t1 t1 @ ( Nodo  x1  L1  r1 )  ` unión `  t2 @ ( Nodo  x2  l2  r2 )  |  x1  <=  x2  =  Nodo  x1  ( t2 ` Unión `  r1 )  l1  |  de lo contrario  =  Nodo  x2  ( t1  ` unión `  r2 )  l2inserte  ::  Ord  un  =>  una  ->  SkewHeap  un  ->  SkewHeap  un inserto  x  montón  =  Singleton  x  ` unión `  montónextractMin  ::  Ord  un  =>  SkewHeap  un  ->  Tal vez  ( una ,  SkewHeap  una ) extractMin  Vacía  =  Nada extractMin  ( Nodo  x  l  r )  =  Justo  ( x ,  l  ` unión `  r )

Referencias

1. Sleator, Daniel Dominic ; Tarjan, Robert Endre (febrero de 1986). "Montones autoajustables" . Revista SIAM de Computación . 15 (1): 52–69. CiteSeerX  10.1.1.93.6678 . doi : 10.1137 / 0215004 . ISSN  0097-5397 .
2. Kaldewaij, Anne; Schoenmakers, Berry (1991). "La derivación de un límite más estricto para montones sesgados de arriba hacia abajo" (PDF) . Cartas de procesamiento de información . 37 (5): 265-271. CiteSeerX 10.1.1.56.8717 . doi : 10.1016 / 0020-0190 (91) 90218-7 .  
3. Schoenmakers, Berry (1997). "Un límite inferior estrecho para montones sesgados de arriba hacia abajo" (PDF) . Cartas de procesamiento de información . 61 (5): 279–284. CiteSeerX 10.1.1.47.447 . doi : 10.1016 / S0020-0190 (97) 00028-8 .  

enlaces externos

• Apuntes de conferencias, Skew Heaps, Universidad de York
• Animaciones que comparan montones de izquierdas y montones de sesgos, Universidad de York
• Simulación de montón de sesgo de Javascript, Universidad de San Francisco
• Applet de Java para simular montones, Kansas State University