Queap
En informática , una cola es una estructura de datos de cola de prioridad . La estructura de datos permite inserciones y eliminaciones de elementos arbitrarios, así como la recuperación del elemento de mayor prioridad. Cada eliminación tiene un tiempo amortizado logarítmico en el número de elementos que han estado en la estructura durante más tiempo que el elemento eliminado. Las inserciones toman un tiempo amortizado constante.
La estructura de datos consta de una lista doblemente enlazada y una estructura de datos de árbol de 2 a 4 , cada una modificada para realizar un seguimiento 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.
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 más tiempo que el elemento. para ser extraído. 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 an - 1 - w ( x ) y w ( x ) es el número de elementos distintos a los que se ha accedido mediante operaciones como buscar, insertar o eliminar. q ( x) se define como cuántos elementos no se han accedido desde el último acceso de x . De hecho, la propiedad queueish es el complemento de la propiedad del conjunto de trabajo del árbol de expansión: el tiempo para buscar el elemento x es O (lg w ( x )).
Una cola se puede representar 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 mínima. La cola mantiene un puntero al elemento mínimo almacenado en la lista. Para agregar el elemento x a la lista l , el elemento x se agrega 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 de 2 a 4 cuando se produce una operación de eliminación. Si el elemento x ya está en el árbol T , el elemento se elimina mediante la operación de eliminación de 2–4 árboles. De lo contrario, el elemento x está en la lista L (se hace comprobando si la variable de bit está establecida). Todos los elementos almacenados en la lista L se agregan al árbol 2-4, estableciendo la variable de bit de cada elemento en cero. x se retira entonces de T .
