En informática , una cola de prioridad de dos extremos (DEPQ) [1] o un montón de dos extremos [2] es una estructura de datos similar a una cola de prioridad o montón , pero permite la eliminación eficiente tanto del máximo como del mínimo, de acuerdo con algunos pedidos sobre las claves (elementos) almacenados en la estructura. Cada elemento de un DEPQ tiene una prioridad o un valor. En un DEPQ, es posible eliminar los elementos tanto en orden ascendente como descendente. [3]
Operaciones
Una cola de prioridad de dos extremos presenta las siguientes operaciones:
- esta vacio()
- Comprueba si DEPQ está vacío y devuelve verdadero si está vacío.
- Talla()
- Devuelve el número total de elementos presentes en el DEPQ.
- getMin ()
- Devuelve el elemento que tiene la menor prioridad.
- getMax ()
- Devuelve el elemento que tiene la prioridad más alta.
- poner ( x )
- Inserta el elemento x en el DEPQ.
- removeMin ()
- Elimina un elemento con prioridad mínima y devuelve este elemento.
- removeMax ()
- Elimina un elemento con máxima prioridad y devuelve este elemento.
Si se va a realizar una operación en dos elementos que tienen la misma prioridad, entonces se elige el elemento insertado primero. Además, la prioridad de cualquier elemento se puede cambiar una vez que se ha insertado en el DEPQ. [4]
Implementación
Las colas de prioridad de dos extremos se pueden construir a partir de árboles de búsqueda binarios balanceados (donde los elementos mínimo y máximo son las hojas más a la izquierda y más a la derecha, respectivamente), o usando estructuras de datos especializadas como el montón mínimo-máximo y el montón de emparejamiento .
Los métodos genéricos para llegar a las colas de prioridad de dos extremos desde las colas de prioridad normales son: [5]
Método de estructura dual
En este método, se mantienen dos colas de prioridad diferentes para mínimo y máximo. Los mismos elementos en ambas PQ se muestran con la ayuda de punteros de correspondencia.
Aquí, los elementos mínimo y máximo son valores contenidos en los nodos raíz de min heap y max heap respectivamente.
- Eliminación del elemento mínimo : ejecute removemin () en el montón mínimo y elimine ( valor del nodo ) en el montón máximo, donde el valor del nodo es el valor en el nodo correspondiente en el montón máximo.
- Eliminación del elemento máximo : realice removemax () en el montón máximo y elimine ( valor del nodo ) en el montón mínimo, donde el valor del nodo es el valor en el nodo correspondiente en el montón mínimo.
Correspondencia total
La mitad de los elementos están en el PQ mínimo y la otra mitad en el PQ máximo. Cada elemento en el PQ mínimo tiene una correspondencia uno a uno con un elemento en el PQ máximo. Si el número de elementos del DEPQ es impar, uno de los elementos se retiene en un búfer. [1] La prioridad de cada elemento en el PQ mínimo será menor o igual que el elemento correspondiente en el PQ máximo.
Correspondencia de hojas
En este método, solo los elementos hoja del PQ mínimo y máximo forman los pares uno a uno correspondientes. No es necesario que los elementos que no sean hojas estén en un par de correspondencia uno a uno. [1]
Montones de intervalos
Aparte de los métodos de correspondencia mencionados anteriormente, los DEPQ se pueden obtener de manera eficiente utilizando montones de intervalos. [6] Un montón de intervalo es como un montón incrustado mínimo-máximo en el que cada nodo contiene dos elementos. Es un árbol binario completo en el que: [6]
- El elemento de la izquierda es menor o igual que el elemento de la derecha.
- Ambos elementos definen un intervalo cerrado.
- El intervalo representado por cualquier nodo excepto la raíz es un subintervalo del nodo principal.
- Los elementos del lado izquierdo definen un montón mínimo .
- Los elementos del lado derecho definen un montón máximo .
Dependiendo del número de elementos, son posibles dos casos [6] -
- Número par de elementos: en este caso, cada nodo contiene dos elementos, digamos p y q , con p ≤ q . Entonces, cada nodo está representado por el intervalo [ p , q ].
- Número impar de elementos: en este caso, cada nodo excepto el último contiene dos elementos representados por el intervalo [ p , q ] mientras que el último nodo contendrá un solo elemento y está representado por el intervalo [ p , p ].
Insertar un elemento
Dependiendo del número de elementos ya presentes en el montón de intervalo, son posibles los siguientes casos:
- Número impar de elementos: si el número de elementos en el montón de intervalo es impar, el nuevo elemento se inserta primero en el último nodo. Luego, se compara sucesivamente con los elementos de nodo anteriores y se prueba para satisfacer los criterios esenciales para un montón de intervalos como se indicó anteriormente. En caso de que el elemento no cumpla con alguno de los criterios, se mueve desde el último nodo a la raíz hasta que se cumplan todas las condiciones. [6]
- Número par de elementos: si el número de elementos es par, se crea un nodo adicional para la inserción de un nuevo elemento. Si el elemento cae a la izquierda del intervalo principal, se considera que está en el montón mínimo y si el elemento cae a la derecha del intervalo principal, se considera en el montón máximo . Además, se compara sucesivamente y se mueve desde el último nodo a la raíz hasta que se satisfacen todas las condiciones para el montón de intervalo. Si el elemento se encuentra dentro del intervalo del propio nodo padre, el proceso se detiene en ese mismo momento y no se produce el movimiento de los elementos. [6]
El tiempo necesario para insertar un elemento depende del número de movimientos necesarios para cumplir todas las condiciones y es O (log n ).
Eliminar un elemento
- Elemento mínimo: en un montón de intervalo, el elemento mínimo es el elemento en el lado izquierdo del nodo raíz. Este elemento se elimina y se devuelve. Para llenar la vacante creada en el lado izquierdo del nodo raíz, se elimina un elemento del último nodo y se vuelve a insertar en el nodo raíz. A continuación, este elemento se compara sucesivamente con todos los elementos de la izquierda de los nodos descendentes y el proceso se detiene cuando se cumplen todas las condiciones para un montón de intervalo. En caso de que el elemento del lado izquierdo en el nodo sea mayor que el elemento del lado derecho en cualquier etapa, los dos elementos se intercambian [6] y luego se hacen más comparaciones. Finalmente, el nodo raíz contendrá nuevamente el elemento mínimo en el lado izquierdo.
- Elemento máximo: en un montón de intervalo, el elemento máximo es el elemento en el lado derecho del nodo raíz. Este elemento se elimina y se devuelve. Para llenar la vacante creada en el lado derecho del nodo raíz, se elimina un elemento del último nodo y se vuelve a insertar en el nodo raíz. Se llevan a cabo comparaciones adicionales sobre una base similar a la discutida anteriormente. Finalmente, el nodo raíz contendrá nuevamente el elemento máximo en el lado derecho.
Por lo tanto, con montones de intervalo, tanto los elementos mínimos como los máximos se pueden eliminar de manera eficiente pasando de la raíz a la hoja. Por lo tanto, se puede obtener un DEPQ [6] a partir de un montón de intervalo donde los elementos del montón de intervalo son las prioridades de los elementos del DEPQ.
Complejidad del tiempo
Montones de intervalos
Cuando los DEPQ se implementan utilizando montones de intervalos que constan de n elementos, las complejidades de tiempo para las diversas funciones se formulan en la siguiente tabla [1]
Operación | Complejidad del tiempo |
---|---|
en eso( ) | En) |
esta vacio( ) | O (1) |
getmin () | O (1) |
getmax () | O (1) |
Talla( ) | O (1) |
insertar (x) | O (log n ) |
removeMin () | O (log n ) |
removeMax () | O (log n ) |
Emparejamiento de montones
Cuando los DEPQ se implementan utilizando montones o montones de emparejamiento que constan de n elementos, las complejidades de tiempo para las diversas funciones se formulan en la siguiente tabla. [1] Para emparejar montones, es una complejidad amortizada .
Operación | Complejidad del tiempo |
---|---|
esta vacio( ) | O (1) |
getmin () | O (1) |
getmax () | O (1) |
insertar (x) | O (log n ) |
removeMax () | O (log n ) |
removeMin () | O (log n ) |
Aplicaciones
Clasificación externa
Una aplicación de ejemplo de la cola de prioridad de dos extremos es la clasificación externa . En un orden externo, hay más elementos de los que se pueden almacenar en la memoria de la computadora. Los elementos que se van a clasificar están inicialmente en un disco y la secuencia ordenada se debe dejar en el disco. La clasificación rápida externa se implementa utilizando el DEPQ de la siguiente manera:
- Lea todos los elementos que quepan en un DEPQ interno. Los elementos del DEPQ eventualmente serán el grupo intermedio (pivote) de elementos.
- Lea los elementos restantes. Si el siguiente elemento es ≤ el elemento más pequeño en el DEPQ, genere este siguiente elemento como parte del grupo de la izquierda. Si el siguiente elemento es ≥ el elemento más grande en el DEPQ, genere este siguiente elemento como parte del grupo correcto. De lo contrario, elimine el elemento máximo o mínimo del DEPQ (la elección puede hacerse al azar o alternativamente); si se quita el elemento máximo, expóngalo como parte del grupo correcto; de lo contrario, envíe el elemento eliminado como parte del grupo de la izquierda; inserte el nuevo elemento de entrada en el DEPQ.
- Imprima los elementos en el DEPQ, en orden ordenado, como el grupo intermedio.
- Ordene los grupos izquierdo y derecho de forma recursiva.
Ver también
Referencias
- ^ a b c d e f g h Estructuras de datos, algoritmos y aplicaciones en Java: colas de prioridad de doble extremo , Sartaj Sahni , 1999.
- ^ Latón, Peter (2008). Estructuras de datos avanzadas . Prensa de la Universidad de Cambridge. pag. 211. ISBN 9780521880374.
- ^ "Depq - Cola de prioridad de doble extremo" . Archivado desde el original el 25 de abril de 2012 . Consultado el 4 de octubre de 2011 .
- ^ "depq" .
- ^ Fundamentos de estructuras de datos en C ++ - Ellis Horowitz, Sartaj Sahni y Dinesh Mehta
- ^ a b c d e f g http://www.mhhe.com/engcs/compsci/sahni/enrich/c9/interval.pdf