COLA DE PRIORIDAD (ESTRUCTURAS DE DATOS)

Una cola de prioridad es un tipo de datos abstracto que se comporta de manera similar a la cola normal excepto que cada elemento tiene cierta prioridad, es decir, el elemento con mayor prioridad ocuparía el primer lugar en una cola de prioridad. La prioridad de los elementos en una cola de prioridad determinará el orden en que se eliminan los elementos de la cola de prioridad.

La cola de prioridad solo admite elementos comparables, lo que significa que los elementos están organizados en orden ascendente o descendente.

leer desde un archivo csv en java

Por ejemplo, supongamos que tenemos algunos valores como 1, 3, 4, 8, 14, 22 insertados en una cola de prioridad con un orden impuesto a los valores que va de menor a mayor. Por lo tanto, el número 1 tendría la mayor prioridad mientras que el 22 tendrá la menor prioridad.

Características de una cola prioritaria

Una cola prioritaria es una extensión de una cola que contiene las siguientes características:

Cada elemento de una cola de prioridad tiene alguna prioridad asociada.
Un elemento con mayor prioridad se eliminará antes de eliminar el de menor prioridad.
Si dos elementos en una cola de prioridad tienen la misma prioridad, se organizarán utilizando el principio FIFO.

Entendamos la cola de prioridad a través de un ejemplo.

Tenemos una cola de prioridad que contiene los siguientes valores:

1, 3, 4, 8, 14, 22

Todos los valores están ordenados en orden ascendente. Ahora observaremos cómo quedará la cola de prioridad después de realizar las siguientes operaciones:

encuesta():Esta función eliminará el elemento de mayor prioridad de la cola de prioridad. En la cola de prioridad anterior, el elemento '1' tiene la prioridad más alta, por lo que será eliminado de la cola de prioridad.agregar(2):Esta función insertará el elemento '2' en una cola de prioridad. Como 2 es el elemento más pequeño entre todos los números, obtendrá la mayor prioridad.encuesta():Eliminará el elemento '2' de la cola de prioridad, ya que tiene la cola de mayor prioridad.agregar(5):Insertará 5 elementos después de 4 ya que 5 es mayor que 4 y menor que 8, por lo que obtendrá la tercera prioridad más alta en una cola de prioridad.

Tipos de cola prioritaria

Hay dos tipos de cola prioritaria:

Representación de cola prioritaria.

Ahora veremos cómo representar la cola de prioridad a través de una lista unidireccional.

Crearemos la cola de prioridad utilizando la lista que se proporciona a continuación en la que INFORMACIÓN la lista contiene los elementos de datos, PRN La lista contiene los números de prioridad de cada elemento de datos disponible en el INFORMACIÓN lista, y LINK básicamente contiene la dirección del siguiente nodo.

Creemos la cola de prioridad paso a paso.

borrando caché npm

En el caso de una cola de prioridad, el número de prioridad más bajo se considera la prioridad más alta, es decir, número de prioridad más baja = prioridad más alta.

Paso 1: En la lista, el número de menor prioridad es 1, cuyo valor de datos es 333, por lo que se insertará en la lista como se muestra en el siguiente diagrama:

Paso 2: Después de insertar 333, la prioridad número 2 tiene una prioridad más alta y los valores de datos asociados con esta prioridad son 222 y 111. Por lo tanto, estos datos se insertarán según el principio FIFO; por lo tanto primero se sumarán 222 y luego 111.

Paso 3: Después de insertar los elementos de prioridad 2, el siguiente número de prioridad superior es 4 y los elementos de datos asociados con 4 números de prioridad son 444, 555, 777. En este caso, los elementos se insertarían según el principio FIFO; por lo tanto, primero se sumarán 444, luego 555 y luego 777.

Etapa 4: Después de insertar los elementos de prioridad 4, el siguiente número de prioridad superior es 5 y el valor asociado con la prioridad 5 es 666, por lo que se insertará al final de la cola.

Implementación de cola de prioridad

La cola de prioridad se puede implementar de cuatro formas que incluyen matrices, lista vinculada, estructura de datos de montón y árbol de búsqueda binaria. La estructura de datos del montón es la forma más eficiente de implementar la cola de prioridad, por lo que implementaremos la cola de prioridad utilizando una estructura de datos del montón en este tema. Ahora, primero entendemos la razón por la cual el montón es la forma más eficiente entre todas las demás estructuras de datos.

Análisis de complejidades utilizando diferentes implementaciones.

Implementación	agregar	Eliminar	ojeada
Lista enlazada	O(1)	En)	En)
montón binario	O(iniciar sesión)	O(iniciar sesión)	O(1)
Árbol de búsqueda binaria	O(iniciar sesión)	O(iniciar sesión)	O(1)

¿Qué es el montón?

Un montón es una estructura de datos basada en árbol que forma un árbol binario completo y satisface la propiedad del montón. Si A es un nodo padre de B, entonces A está ordenado con respecto al nodo B para todos los nodos A y B en un montón. Significa que el valor del nodo principal podría ser mayor o igual que el valor del nodo secundario, o el valor del nodo principal podría ser menor o igual que el valor del nodo secundario. Por tanto, podemos decir que existen dos tipos de montones:

Ambos montones son binarios, ya que cada uno tiene exactamente dos nodos secundarios.

Operaciones de cola prioritarias

Las operaciones comunes que podemos realizar en una cola de prioridad son inserción, eliminación y vista. Veamos cómo podemos mantener la estructura de datos del montón.

Insertar el elemento en una cola de prioridad (montón máximo)

Si insertamos un elemento en una cola de prioridad, se moverá al espacio vacío mirando de arriba a abajo y de izquierda a derecha.

Si el elemento no está en el lugar correcto, se compara con el nodo principal; si se encuentra fuera de servicio, se intercambian los elementos. Este proceso continúa hasta que el elemento se coloca en una posición correcta.

Eliminar el elemento mínimo de la cola de prioridad

Como sabemos, en un montón máximo, el elemento máximo es el nodo raíz. Cuando eliminamos el nodo raíz, se crea una ranura vacía. El último elemento insertado se agregará en este espacio vacío. Luego, este elemento se compara con los nodos secundarios, es decir, el hijo izquierdo y el hijo derecho, y se intercambia con el más pequeño de los dos. Sigue bajando por el árbol hasta que se restablece la propiedad del montón.

Aplicaciones de cola prioritaria

Las siguientes son las aplicaciones de la cola prioritaria:

conjunto de hash java

Se utiliza en el algoritmo del camino más corto de Dijkstra.
Se utiliza en el algoritmo de prim.
Se utiliza en técnicas de compresión de datos como el código Huffman.
Se utiliza en clasificación de montón.
También se utiliza en sistemas operativos como programación de prioridades, equilibrio de carga y manejo de interrupciones.

Programa para crear la cola de prioridad utilizando el montón máximo binario.

 #include #include int heap[40]; int size=-1; // retrieving the parent node of the child node int parent(int i) { return (i - 1) / 2; } // retrieving the left child of the parent node. int left_child(int i) { return i+1; } // retrieving the right child of the parent int right_child(int i) { return i+2; } // Returning the element having the highest priority int get_Max() { return heap[0]; } //Returning the element having the minimum priority int get_Min() { return heap[size]; } // function to move the node up the tree in order to restore the heap property. void moveUp(int i) { while (i &gt; 0) { // swapping parent node with a child node if(heap[parent(i)] <heap[i]) 2 { int temp; temp="heap[parent(i)];" heap[parent(i)]="heap[i];" heap[i]="temp;" } updating the value of i to function move node down tree in order restore heap property. void movedown(int k) index="k;" getting location left child if (left heap[index]) right (right k is not equal (k !="index)" heap[index]="heap[k];" heap[k]="temp;" movedown(index); removing element maximum priority removemax() r="heap[0];" heap[0]="heap[size];" size="size-1;" movedown(0); inserting a queue insert(int p) + 1; heap[size]="p;" up maintain property moveup(size); from at given i. delete(int i) stored ith shifted root moveup(i); having removemax(); main() elements insert(20); insert(19); insert(21); insert(18); insert(12); insert(17); insert(15); insert(16); insert(14); printf('elements are : '); for(int printf('%d ',heap[i]); delete(2); deleting whose 2. printf('
elements after max="get_Max();" printf('
the which highest %d: ',max); min="get_Min();" minimum %d',min); return 0; < pre> <p> <strong>In the above program, we have created the following functions:</strong> </p> <ul> <tr><td>int parent(int i):</td> This function returns the index of the parent node of a child node, i.e., i. </tr><tr><td>int left_child(int i):</td> This function returns the index of the left child of a given index, i.e., i. </tr><tr><td>int right_child(int i):</td> This function returns the index of the right child of a given index, i.e., i. </tr><tr><td>void moveUp(int i):</td> This function will keep moving the node up the tree until the heap property is restored. </tr><tr><td>void moveDown(int i):</td> This function will keep moving the node down the tree until the heap property is restored. </tr><tr><td>void removeMax():</td> This function removes the element which is having the highest priority. </tr><tr><td>void insert(int p):</td> It inserts the element in a priority queue which is passed as an argument in a function <strong>.</strong>  </tr><tr><td>void delete(int i):</td> It deletes the element from a priority queue at a given index. </tr><tr><td>int get_Max():</td> It returns the element which is having the highest priority, and we know that in max heap, the root node contains the element which has the largest value, and highest priority. </tr><tr><td>int get_Min():</td> It returns the element which is having the minimum priority, and we know that in max heap, the last node contains the element which has the smallest value, and lowest priority. </tr></ul> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/what-is-priority-queue-9.webp" alt="Priority Queue"> <hr></heap[i])>

TechCodeview

¿Qué es una cola prioritaria?