Cola de prioridad en la estructura de datos: características, tipos e implementación
Publicado: 2021-05-02Tabla de contenido
Introducción
La cola de prioridad en la estructura de datos es una extensión de la cola "normal". Es un tipo de datos abstracto que contiene un grupo de elementos. Es como la cola "normal", excepto que los elementos que se quitan de la cola siguen un orden de prioridad. El orden de prioridad elimina primero los elementos que tienen la prioridad más alta. Este blog le brindará una comprensión más profunda de la cola de prioridad y su implementación en el lenguaje de programación C.
¿Qué es una cola de prioridad?
Es un tipo de datos abstracto que proporciona una forma de mantener el conjunto de datos. La cola "normal" sigue un patrón de primero en entrar, primero en salir. Saca elementos de la cola en el mismo orden seguido en el momento de la operación de inserción. Sin embargo, el orden de los elementos en una cola de prioridad depende de la prioridad del elemento en esa cola. La cola de prioridad mueve los elementos de mayor prioridad al principio de la cola de prioridad y los elementos de menor prioridad al final de la cola de prioridad.
Solo admite aquellos elementos que son comparables. Por lo tanto, una cola de prioridad en la estructura de datos organiza los elementos en orden ascendente o descendente.
Puede pensar en una fila de prioridad como varios pacientes esperando en la fila de un hospital. Aquí, la situación del paciente define el orden de prioridad. El paciente con la lesión más grave sería el primero en la cola.
¿Cuáles son las características de una cola de prioridad?
Una cola se denomina cola de prioridad si tiene las siguientes características:
- Cada elemento tiene alguna prioridad asociada con él.
- Un elemento con la prioridad más alta se mueve al frente y se elimina primero.
- Si dos elementos comparten el mismo valor de prioridad, entonces la cola de prioridad sigue el principio de primero en entrar, primero en salir para la operación de cola.
¿Cuáles son los tipos de cola de prioridad?
Una cola de prioridad es de dos tipos:
- Cola de prioridad de orden ascendente
- Cola de prioridad de orden descendente
Cola de prioridad de orden ascendente
Una cola de prioridad en orden ascendente da la prioridad más alta al número más bajo en esa cola. Por ejemplo, tiene seis números en la cola de prioridad que son 4, 8, 12, 45, 35, 20. Primero, ordenará estos números en orden ascendente. La nueva lista es la siguiente: 4, 8, 12, 20. 35, 45. En esta lista, 4 es el número más pequeño. Por lo tanto, la cola de prioridad en orden ascendente trata el número 4 como la prioridad más alta.
| 4 | 8 | 12 | 20 | 35 | 45 |
En la tabla anterior, 4 tiene la prioridad más alta y 45 tiene la prioridad más baja.
Cola de prioridad de orden descendente
Una cola de prioridad en orden descendente da la prioridad más alta al número más alto en esa cola. Por ejemplo, tiene seis números en la cola de prioridad que son 4, 8, 12, 45, 35, 20. Primero, ordenará estos números en orden ascendente. La nueva lista es la siguiente: 45, 35, 20, 12, 8, 4. En esta lista, 45 es el número más alto. Por lo tanto, la cola de prioridad en orden descendente trata el número 45 como la prioridad más alta.
| 45 | 35 | 20 | 12 | 8 | 4 |
En la tabla anterior, 4 tiene la prioridad más baja y 45 tiene la prioridad más alta.
Implementación de la cola de prioridad en la estructura de datos
Puede implementar las colas de prioridad de una de las siguientes maneras:
- Lista enlazada
- montón binario
- arreglos
- Árbol de búsqueda binario
El montón binario es el método más eficiente para implementar la cola de prioridad en la estructura de datos .
Las siguientes tablas resumen la complejidad de las diferentes operaciones en una cola de prioridad.
| Operación | Matriz desordenada | matriz ordenada | montón binario | Árbol de búsqueda binaria |
| Insertar | 0(1) | 0(N) | 0(registro(N)) | 0(registro(N)) |
| Ojeada | 0(N) | 0(1) | 0(1) | 0(1) |
| Borrar | 0(N) | 0(1) | 0 (registro (N)) | 0(registro(N)) |
montón binario
Un árbol de montón binario organiza todos los nodos principales y secundarios del árbol en un orden particular. En un árbol de montón binario, un nodo principal puede tener un máximo de 2 nodos secundarios. El valor del nodo principal podría ser:
- igual o menor que el valor de un nodo hijo.
- igual o mayor que el valor de un nodo secundario.
El proceso anterior divide el montón binario en dos tipos: montón máximo y montón mínimo.
Montón máximo
El montón máximo es un montón binario en el que un nodo principal tiene un valor igual o mayor que el valor del nodo secundario. El nodo raíz del árbol tiene el valor más alto.
Inserción de un elemento en un árbol binario Max Heap
Puede realizar los siguientes pasos para insertar un elemento/número en la cola de prioridad en la estructura de datos .
- El algoritmo escanea el árbol de arriba a abajo y de izquierda a derecha para encontrar un espacio vacío. Luego inserta el elemento en el último nodo del árbol.
- Después de insertar el elemento, se altera el orden del árbol binario. Debe intercambiar los datos entre sí para clasificar el orden del árbol binario del montón máximo. Debe seguir mezclando los datos hasta que el árbol satisfaga la propiedad max-heap.
Algoritmo para insertar un elemento en un árbol binario Max Heap
Si el árbol está vacío y no contiene ningún nodo,
crear un nuevo nodo padre newElement.
else (un nodo principal ya está disponible)
inserte el elemento nuevo al final del árbol (es decir, el último nodo del árbol de izquierda a derecha).
max-heapificar el árbol
Eliminación de un elemento en un árbol binario Max Heap
- Puede realizar los siguientes pasos para eliminar un elemento en la cola de prioridad en la estructura de datos .
- Elija el elemento que desea eliminar del árbol binario.
- Desplace los datos al final del árbol intercambiándolos con los datos del último nodo.
- Elimina el último elemento del árbol binario.
- Después de eliminar el elemento, se altera el orden del árbol binario. Debe ordenar el orden para satisfacer la propiedad de max-heap. Debe seguir mezclando los datos hasta que el árbol cumpla con la propiedad max-heap.
Algoritmo para eliminar un elemento en un árbol binario Max Heap
Si elementUpForDeletion es el último nodo,
eliminar el elementoUpForDeletion
de lo contrario, reemplace elementUpForDeletion con lastNode
eliminar el elementoUpForDeletion
max-heapificar el árbol
Encuentre el elemento máximo o mínimo en un árbol binario de Max Heap
En un árbol binario de almacenamiento dinámico máximo, la operación de búsqueda devuelve el nodo principal (el elemento más alto) del árbol.
Algoritmo para encontrar el máximo o mínimo en un árbol binario de montón máximo
devolver ParentNode
Implementación del programa de la cola de prioridad utilizando el árbol binario Max Heap
| #incluir <stdio.h> int árbol_binario = 10; int max_heap = 0; prueba int constante = 100000;
intercambio vacío (int *x, int *y) { en un; a = *x; *x= *y; *y = un; }
//Código para encontrar el padre en el árbol de almacenamiento dinámico máximo int findParentNode(int nodo[], int raíz) { if ((raíz > 1) && (raíz < árbol_binario)) { devolver raíz/2; } devolver -1; }
void max_heapify(int nodo[], int raíz) { int leftNodeRoot = findLeftChild(nodo, raíz); int rightNodeRoot = findRightChild(nodo, raíz);
// encontrar el más alto entre la raíz, el hijo izquierdo y el hijo derecho int más alto = raíz;
if ((raíz del nodo izquierdo <= max_heap) && (raíz del nodo izquierdo > 0)) { if (nodo[nodoraízizquierdo] > nodo[más alto]) { más alto = raíz del nodo izquierdo; } }
if ((rightNodeRoot <= max_heap) && (rightNodeRoot >0)) { if (nodo[rightNodeRoot] > nodo[más alto]) { más alto = rightNodeRoot; } }
if (más alto! = raíz) { swap(&nodo[raíz], &nodo[más alto]); max_heapify(nodo, más alto); } }
void create_max_heap(int nodo[]) { int d; for(d=max_heap/2; d>=1; d–) { max_heapify(nodo, d); } }
int máximo(int nodo[]) { nodo de retorno[1]; }
int find_max(int nodo[]) { int maxNode = nodo[1]; nodo[1] = nodo[max_heap]; max_heap–; max_heapify(nodo, 1); volver maxNode; } void descend_key(int nodo[], int nodo, int clave) { A[raíz] = clave; max_heapify(nodo, raíz); } void aumentar_clave(int nodo[], int raíz, int clave) { nodo[raíz] = clave; while((raíz>1) && (nodo[buscarNodoParent(nodo, raíz)] < nodo[raíz])) { swap(&nodo[raíz], &nodo[buscarNodoParent(nodo, raíz)]); root = findParentNode(nodo, raíz); } }
inserción vacía (nodo int [], clave int) { max_heap++; nodo[max_heap] = -1*prueba; aumentar_clave(nodo, max_heap, clave); }
void display_heap(int nodo[]) { int d; for(d=1; d<=montón_máximo; d++) { printf(“%d\n”,nodo[d]); } imprimirf(“\n”); }
int principal() { int nodo[árbol_binario]; insertar(nodo, 10); insertar(nodo, 4); insertar(nodo, 20); insertar(nodo, 50); insertar(nodo, 1); insertar(nodo, 15);
display_heap(nodo);
printf(“%d\n\n”, maximo(nodo)); display_heap(nodo);
printf(“%d\n”, extract_max(nodo)); printf(“%d\n”, extract_max(nodo)); devolver 0; } |
Montón mínimo
El montón mínimo es un montón binario en el que un nodo principal tiene un valor igual o menor que el valor del nodo secundario. El nodo raíz del árbol tiene el valor más bajo.
Puede implementar el montón mínimo de la misma manera que el montón máximo, excepto en el orden inverso.
Conclusión
Los ejemplos dados en el artículo son solo para fines explicativos. Puede modificar las declaraciones anteriores según sus requisitos. En este blog, aprendimos sobre el concepto de cola de prioridad en la estructura de datos . Puede probar el ejemplo para fortalecer su conocimiento de la estructura de datos.
Si tiene curiosidad por aprender sobre ciencia de datos, consulte el Programa ejecutivo PG en ciencia de datos de IIIT-B y upGrad, creado para profesionales que trabajan y ofrece más de 10 estudios de casos y proyectos, talleres prácticos, tutoría con expertos de la industria, 1 -on-1 con mentores de la industria, más de 400 horas de aprendizaje y asistencia laboral con las mejores empresas.
Aprenda cursos de ciencia de datos en línea de las mejores universidades del mundo. Obtenga programas Executive PG, programas de certificados avanzados o programas de maestría para acelerar su carrera.
La cola de prioridad es una cola especial donde los elementos se insertan en función de su prioridad. Esta característica llega a ser útil en la implementación de varias otras estructuras de datos. Las siguientes son algunas de las aplicaciones más populares de la cola de prioridad: El enfoque utilizado en la implementación de la cola de prioridad mediante una matriz es simple. Se crea una estructura para almacenar los valores y la prioridad del elemento y luego se crea la matriz de esa estructura para almacenar los elementos. Las siguientes operaciones están involucradas en esta implementación: A continuación, se ilustra la diferencia entre el montón máximo y el montón mínimo.¿Cuáles son las aplicaciones de una cola de prioridad?
1. Algoritmo de ruta más corta de Dijkstra: la cola de prioridad se puede utilizar en el algoritmo de ruta más corta de Dijkstra cuando el gráfico se almacena en forma de lista de adyacencia.
2. Algoritmo de Prim: el algoritmo de Prim utiliza la cola de prioridad para los valores o claves de los nodos y extrae el mínimo de estos valores en cada paso.
Compresión de datos : los códigos de Huffman utilizan la cola de prioridad para comprimir los datos.
Sistemas operativos: la cola de prioridad es muy útil para los sistemas operativos en varios procesos, como el equilibrio de carga y el manejo de interrupciones. ¿Qué enfoque se usa en la implementación de la cola de prioridad usando una matriz?
1. enqueue(): esta función inserta los elementos al final de la cola.
2. peek(): esta función recorrerá la matriz para devolver el elemento con la prioridad más alta. Si encuentra dos elementos que tienen la misma prioridad, devuelve el elemento de mayor valor entre ellos.
3. dequeue(): esta función desplazará todos los elementos, 1 posición a la izquierda del elemento devuelto por la función peek() y disminuirá el tamaño. ¿Cuál es la diferencia entre el montón máximo y el montón mínimo?
Montón mínimo: en un montón mínimo, la clave del nodo raíz debe ser menor o igual que las claves de su nodo secundario. Utiliza prioridad ascendente. El nodo con la clave más pequeña es la prioridad. El elemento más pequeño aparece antes que cualquier otro elemento.
Montón máximo: en un montón máximo, la clave del nodo raíz debe ser mayor o igual que la clave de los nodos secundarios. Utiliza prioridad descendente. El nodo con la clave más grande es la prioridad. El elemento más grande aparece antes que cualquier otro elemento.