Quejarse

Una Queap Q con k = 6 y n = 9

En informática , una cola es una estructura de datos de cola de prioridad . La estructura de datos permite la inserción y eliminación de elementos arbitrarios, así como la recuperación del elemento de mayor prioridad. Cada eliminación lleva un tiempo amortizado logarítmico en la cantidad de elementos que han estado en la estructura durante un tiempo mayor que el elemento eliminado. Las inserciones llevan un tiempo amortizado constante.

La estructura de datos consta de una lista doblemente enlazada y una estructura de datos de árbol 2-4 , cada una modificada para llevar un registro de su elemento de prioridad mínima. La operación básica de la estructura es mantener los elementos recién insertados en la lista doblemente enlazada hasta que una eliminación elimine uno de los elementos de la lista, momento en el que todos se mueven al árbol 2-4. El árbol 2-4 almacena sus elementos en orden de inserción, en lugar del orden de prioridad más convencional.

Tanto la estructura de datos como su nombre fueron ideados por John Iacono y Stefan Langerman . ^[1]

Descripción

Una cola es una cola de prioridad que inserta elementos en O (1) tiempo amortizado y elimina el elemento mínimo en O (log( k  + 2)) si hay k elementos que han estado en el montón durante un tiempo mayor que el elemento que se va a extraer. La cola tiene una propiedad llamada propiedad queueish: el tiempo para buscar el elemento x es O(lg q ( x )) donde q ( x ) es igual a n  − 1 −  w ( x ) y w ( x ) es el número de elementos distintos a los que se ha accedido mediante operaciones como búsqueda, inserción o eliminación. q ( x ) se define como la cantidad de elementos a los que no se ha accedido desde el último acceso de x . De hecho, la propiedad queueish es el complemento de la propiedad del conjunto de trabajo del árbol splay: el tiempo para buscar el elemento x es O (lg w ( x )).

Una cola puede representarse mediante dos estructuras de datos: una lista doblemente enlazada y una versión modificada del árbol 2–4. La lista doblemente enlazada, L , se utiliza para una serie de operaciones de inserción y localización-min. La cola mantiene un puntero al elemento mínimo almacenado en la lista. Para añadir el elemento x a la lista l , el elemento x se añade al final de la lista y una variable de bit en el elemento x se establece en uno. Esta operación se realiza para determinar si el elemento está en la lista o en un árbol 2–4.

Se utiliza un árbol 2–4 cuando se produce una operación de eliminación. Si el elemento x ya está en el árbol T , se elimina mediante la operación de eliminación del árbol 2–4. De lo contrario, el elemento x está en la lista L (se realiza comprobando si la variable bit está establecida). Todos los elementos almacenados en la lista L se añaden entonces al árbol 2–4, estableciendo la variable bit de cada elemento en cero. A continuación, x se elimina de T .

Una cola utiliza solo las propiedades de la estructura de árbol 2–4, no un árbol de búsqueda. La estructura de árbol 2–4 modificada es la siguiente. Supongamos que la lista L tiene el siguiente conjunto de elementos: . Cuando se invoca la operación de eliminación, el conjunto de elementos almacenados en L se agrega a las hojas del árbol 2–4 en ese orden, precedido por una hoja ficticia que contiene una clave infinita. Cada nodo interno de T tiene un puntero , que apunta al elemento más pequeño en el subárbol v . Cada nodo interno en la ruta P desde la raíz a tiene un puntero , que apunta a la clave más pequeña en . Los punteros de cada nodo interno en la ruta P se ignoran. La cola tiene un puntero a , que apunta al elemento más pequeño en T . ${\displaystyle x_{1},x_{2},x_{3},\dots ,x_{k}}$ ${\displaystyle h_{v}}$ ${\displaystyle x_{0}}$ ${\displaystyle c_{v}}$ ${\displaystyle T-T_{v}-\{r\}}$ ${\displaystyle h_{v}}$ ${\displaystyle c_{x_{0}}}$

Una aplicación de colas incluye un conjunto único de eventos de alta prioridad y la extracción del evento de mayor prioridad para su procesamiento.

Operaciones

Sea minL un puntero que apunta al elemento mínimo en la lista doblemente enlazada L , sea el elemento mínimo almacenado en el árbol 2–4, T , k sea el número de elementos almacenados en T , y n sea el número total de elementos almacenados en la cola Q . Las operaciones son las siguientes: ${\displaystyle c_{x_{0}}}$

Nuevo(Q): Inicializa una nueva cola vacía.

Inicialice una lista doblemente enlazada vacía L y un árbol 2–4 T. Establezca k y n en cero.

Insertar(Q, x): agrega el elemento x a la cola Q.

Inserta el elemento x en la lista L. Establece el bit del elemento x en uno para demostrar que el elemento está en la lista L. Actualiza el puntero minL si x es el elemento más pequeño de la lista. Incrementa n en 1.

Mínimo (Q): recupera un puntero al elemento más pequeño de lacola Q.

Si clave(minL) < clave ( ), devuelve minL . De lo contrario, devuelve . ${\displaystyle c_{x_{0}}}$ ${\displaystyle c_{x_{0}}}$

Eliminar(Q, x): elimina el elemento x de la cola Q.

Si el bit del elemento x se establece en uno, el elemento se almacena en la lista L . Agregue todos los elementos desde L hasta T , estableciendo el bit de cada elemento en cero. Cada elemento se agrega al padre del hijo más a la derecha de T utilizando la operación de inserción del árbol 2-4. L se vuelve vacío. Actualice los punteros para todos los nodos v cuyos hijos son nuevos/modificados y repita el proceso con el próximo padre hasta que el padre sea igual a la raíz. Vaya desde la raíz al nodo y actualice los valores. Establezca k igual a n . ${\displaystyle h_{v}}$ ${\displaystyle x_{0}}$ ${\displaystyle c_{v}}$

Si el bit del elemento x se establece en cero, x es una hoja de T. Borre x utilizando la operación de borrado del árbol 2–4. Partiendo del nodo x , recorra T hasta el nodo , actualizando los punteros y . Decremente n y k en 1. ${\displaystyle x_{0}}$ ${\displaystyle h_{v}}$ ${\displaystyle c_{v}}$

DeleteMin(Q): elimina y devuelve el elemento más pequeño de la cola Q.

Invocar la operación Minimum(Q) . La operación devuelve min . Invocar la operación Delete(Q, min) . Devuelve min .

CleanUp(Q): elimina todos los elementos de la lista L y delárbol T.

A partir del primer elemento de la lista L , recorra la lista eliminando cada nodo.

Comenzando desde la raíz del árbol T , recorra el árbol utilizando el algoritmo de recorrido post-orden , eliminando cada nodo del árbol.

Análisis

El tiempo de ejecución se analiza mediante el análisis amortizado . La función potencial para la cola Q será donde . ${\displaystyle \phi (Q)=c|L|}$ ${\displaystyle Q=(T,L)}$

Insertar(Q, x): El costo de la operación es O(1) . El tamaño de la lista L aumenta en uno, el potencial aumenta en una constante c .

Mínimo(Q): La operación no altera la estructura de los datos por lo que el coste amortizado es igual a su coste real, O(1).

Eliminar(Q, x): Hay dos casos.

Caso 1

Si x está en el árbol T , entonces el costo amortizado no se modifica. La operación de eliminación es O(1) árbol amortizado 2–4. Dado que x se eliminó del árbol, es posible que sea necesario actualizar los punteros. Como máximo, habrá actualizaciones. ${\displaystyle h_{v}}$ ${\displaystyle c_{v}}$ ${\displaystyle O(lgq(x))}$

Caso 2

Si x está en la lista L , entonces todos los elementos de L se insertan en T . Esto tiene un costo de alguna constante a , amortizada en el árbol 2–4. Después de insertar y actualizar los punteros y , el tiempo total empleado está limitado por . La segunda operación es eliminar x de T , y recorrer el camino desde x hasta , corrigiendo los valores y . El tiempo se emplea como máximo . Si , entonces el costo amortizado será . Delete(Q, x): es la suma del costo amortizado de Minimum(Q) y Delete(Q, x) , que es . ${\displaystyle a|L|}$ ${\displaystyle h_{v}}$ ${\displaystyle c_{v}}$ ${\displaystyle 2a|L|}$ ${\displaystyle x_{0}}$ ${\displaystyle h_{v}}$ ${\displaystyle c_{v}}$ ${\displaystyle 2a|L|+O(lgq(x))}$ ${\displaystyle c>2a}$ ${\displaystyle O(lgq(x))}$ ${\displaystyle O(lgq(x))}$

Ejemplo de código

Una pequeña implementación en Java de una cola:

public class Queap { public int n , k ; public List < Element > l ; // Element es un tipo de datos genérico. public QueapTree t ; // un árbol 2-4, modificado para fines de Queap public Element minL ;                  privado Queap () { n = 0 ; k = 0 ; l = nueva LinkedList < Elemento > (); t = nuevo QueapTree (); }                  público estático Queap New () { devolver nuevo Queap (); }         público estático void Insertar ( Queap Q , Elemento x ) { si ( Q . n == 0 ) Q . minL = x ; Q . l . add ( x ); x . inList = verdadero ; si ( x . compareTo ( Q . minL ) < 0 ) Q . minL = x ; }                           public static Element Minimum ( Queap Q ) { // t es un árbol 2-4 y x0, cv son nodos del árbol. if ( Q ​​. minL . compareTo ( Q . t . x0 . cv . key ) < 0 ) return Q . minL ;             devuelve Q . t . x0 . cv . clave ; }   público estático void Eliminar ( Queap Q , QueapNode x ) { Q . t . deleteLeaf ( x ); -- Q . n ; -- Q . k ; }            public static void Delete ( Queap Q , Element x ) { QueapNode n ; if ( x.inList ) { // establece inList de todos los elementos de la lista en falso n = Q.t.insertList ( Q.l , x ) ; Q.k = Q.n ; Delete ( Q , n ) ; } else if ( ( n = Q.t.x0.cv ) .key == x ) Delete ( Q , n ) ; }​​​                                  public static Element DeleteMin ( Queap Q ) { Elemento min = Mínimo ( Q ); Delete ( Q , min ); return min ; } }              

Véase también

• Cola (estructura de datos)
• Árbol de expansión

Referencias

1. Iacono, John ; Langerman, Stefan (2005). "Queaps". Algorithmica . 42 (1). Springer: 49–56. doi :10.1007/s00453-004-1139-5. S2CID  263883421.