Hispanopedia WikiEn informática , una cola de prioridad de doble extremo (DEPQ) [ 1 ] , un montón de doble extremo [ 2 ] o una DEQ de prioridad es una estructura de datos similar a una cola de prioridad o un montón , pero permite la eliminación eficiente tanto del máximo como del mínimo, según un ordenamiento de las claves (elementos) almacenadas en la estructura. Cada elemento de una DEPQ tiene una prioridad o valor. En una DEPQ, es posible eliminar los elementos tanto en orden ascendente como descendente. [ 3 ]
Operaciones
Una cola de prioridad de doble extremo presenta las siguientes operaciones:
- estáVacío()
- Comprueba si DEPQ está vacío y devuelve verdadero si lo está.
- tamaño()
- Devuelve el número total de elementos presentes en la DEPQ.
- obtenerMínimo()
- Devuelve el elemento con menor prioridad.
- obtenerMáximo()
- Devuelve el elemento con la prioridad más alta.
- poner( x )
- Inserta el elemento x en la cola DEPQ.
- removeMin()
- Elimina el elemento con la prioridad mínima y devuelve dicho elemento.
- removeMax()
- Elimina el elemento con la máxima prioridad y devuelve dicho elemento.
Además, la prioridad de cualquier elemento puede cambiarse una vez que se haya insertado en la DEPQ. [ 4 ]
Implementación
Las colas de prioridad de doble extremo se pueden construir a partir de árboles de búsqueda binaria equilibrados (donde los elementos mínimo y máximo son las hojas más a la izquierda y más a la derecha, respectivamente), o utilizando estructuras de datos especializadas como el montículo min-max y el montículo de emparejamiento .
Los métodos genéricos para llegar a colas de prioridad de doble extremo a partir de colas de prioridad normales son: [ 5 ]
Método de estructura dual
En este método, se mantienen dos colas de prioridad diferentes para el mínimo y el máximo. Los mismos elementos en ambas colas se muestran mediante punteros de correspondencia. En este caso, los elementos mínimo y máximo son los valores contenidos en los nodos raíz del montón mínimo y del montón máximo, respectivamente.
- Eliminar el elemento min : Ejecute removemin() en el montón min y remove( node value ) en el montón max, donde node value es el valor en el nodo correspondiente en el montón max.
- Eliminar el elemento máximo : Ejecute removemax() en el montón máximo y remove( node value ) en el montón mínimo, donde node value es el valor en el nodo correspondiente en el montón mínimo.
Correspondencia total
La mitad de los elementos se encuentran en la cola de prioridad mínima (min PQ) y la otra mitad en la cola de prioridad máxima (max PQ). Cada elemento de la min PQ tiene una correspondencia uno a uno con un elemento de la max PQ. Si el número de elementos en la DEPQ es impar, uno de ellos se retiene en un búfer. [ 1 ] La prioridad de cada elemento de la min PQ será menor o igual que la del elemento correspondiente en la max PQ.
Correspondencia de hojas
A diferencia de una correspondencia total , en este método solo los elementos hoja de la PQ min y max forman pares uno a uno correspondientes. No es necesario que los elementos no hoja estén en un par de correspondencia uno a uno. [ 1 ] Si el número de elementos en la DEPQ es impar, uno de los elementos se retiene en un búfer. [ 1 ]
Montones de intervalos
Además de los métodos de correspondencia mencionados anteriormente, los DEPQ se pueden obtener de manera eficiente utilizando montículos de intervalos. [ 6 ] Un montículo de intervalos es como un montículo min-max incrustado 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 padre.
- 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 . Cada nodo se representa entonces mediante 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 intervalos, son posibles los siguientes casos:
- Número impar de elementos: Si el número de elementos en el montón de intervalos es impar, el nuevo elemento se inserta primero en el último nodo. Luego, se compara sucesivamente con los elementos del nodo anterior y se comprueba si cumple los criterios esenciales para un montón de intervalos, como se indicó anteriormente. En caso de que el elemento no cumpla alguno de los criterios, se mueve del ú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, para la inserción de un nuevo elemento se crea un nodo adicional. Si el elemento se encuentra a la izquierda del intervalo padre, se considera que está en el montón mínimo, y si se encuentra a la derecha, se considera que está en el montón máximo . A continuación, se compara sucesivamente y se mueve desde el último nodo hasta la raíz hasta que se cumplan todas las condiciones del montón de intervalo. Si el elemento se encuentra dentro del intervalo del nodo padre, el proceso se detiene y no se mueven más 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 intervalos, el elemento mínimo es el que se encuentra a la izquierda del nodo raíz. Este elemento se elimina y se devuelve. Para llenar el espacio vacío creado a la izquierda del nodo raíz, se elimina un elemento del último nodo y se reinserta en el nodo raíz. 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 intervalos. Si en algún momento el elemento de la izquierda del nodo se vuelve mayor que el de la derecha, se intercambian los dos elementos [ 6 ] y se realizan más comparaciones. Finalmente, el nodo raíz volverá a contener el elemento mínimo a la izquierda.
- Elemento máximo: En un montón de intervalos, el elemento máximo es el que se encuentra a la derecha del nodo raíz. Este elemento se elimina y se devuelve. Para llenar el espacio vacío creado a la derecha del nodo raíz, se elimina un elemento del último nodo y se reinserta en el nodo raíz. Se realizan comparaciones adicionales de forma similar a la descrita anteriormente. Finalmente, el nodo raíz volverá a contener el elemento máximo a la derecha.
Así, con los montículos de intervalos, tanto el elemento mínimo como el máximo pueden eliminarse eficientemente recorriendo desde la raíz hasta la hoja. Por lo tanto, se puede obtener un DEPQ [ 6 ] a partir de un montículo de intervalos donde los elementos del montículo de intervalos son las prioridades de los elementos del DEPQ.
complejidad temporal
Montones de intervalos
Cuando los DEPQ se implementan utilizando montones de intervalo que constan de n elementos, las complejidades de tiempo para las diversas funciones se formulan en la tabla siguiente [ 1 ].
Montones de emparejamiento
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 tabla siguiente. [ 1 ] Para los montones de emparejamiento, es una complejidad amortizada .
Aplicaciones
Clasificación externa
Un ejemplo de aplicación de la cola de prioridad de doble extremo es la ordenación externa . En una ordenación externa, hay más elementos de los que puede almacenar la memoria del ordenador. Los elementos que se van a ordenar se encuentran inicialmente en un disco y la secuencia ordenada debe permanecer en el disco. La ordenación rápida externa se implementa utilizando la cola de prioridad de doble extremo (DEPQ) de la siguiente manera:
- Se cargarán tantos elementos como quepan en una DEPQ interna. Los elementos de la DEPQ formarán finalmente el grupo central (pivote) de elementos.
- Lee los elementos restantes. Si el siguiente elemento es menor o igual que el elemento más pequeño de la DEPQ, imprímelo como parte del grupo izquierdo. Si el siguiente elemento es mayor o igual que el elemento más grande de la DEPQ, imprímelo como parte del grupo derecho. En caso contrario, elimina el elemento máximo o mínimo de la DEPQ (la elección puede hacerse aleatoriamente o de forma alternada); si se elimina el elemento máximo, imprímelo como parte del grupo derecho; de lo contrario, imprímelo como parte del grupo izquierdo; inserta el nuevo elemento en la DEPQ.
- Muestre los elementos en el DEPQ, en orden ascendente, como el grupo central.
- Ordena los grupos de la izquierda y de la derecha de forma recursiva.
Véase también
Referencias
- 1 2 3 4 5 6 7 8 9 Estructuras de datos, algoritmos y aplicaciones en Java: colas de prioridad de doble extremo , Sartaj Sahni , 1999.
- ↑ Brass, Peter (2008). Estructuras de datos avanzadas . Cambridge University Press. pág. 211. ISBN 9780521880374.
- ↑ "Depq - Cola de prioridad de doble extremo" . Archivado del original el 25/04/2012 . Consultado el 04/10/2011 .
- ↑ "depq" .
- ↑ Fundamentos de estructuras de datos en C++ - Ellis Horowitz, Sartaj Sahni y Dinesh Mehta
- 1 2 3 4 5 6 7 "Apoyo a la educación superior | McGraw Hill" (PDF) . www.mhhe.com . Consultado el 5 de junio de 2026 .
- Tipos de datos abstractos
- Montones (estructuras de datos)
- Colas de prioridad
