Cola de prioridad en C#
Este artículo presentará una cola de prioridad equivalente en C#.
Utilice la Lista como cola de prioridad en C#
En C#, no hay una clase especial para la cola de prioridad. Pero podemos implementarlo usando matrices y listas. Usaremos la estructura de datos de la lista para implementar una cola de prioridad. Una cola de prioridad es un tipo de datos abstracto que tiene una prioridad asociada con sus elementos. La lista se creará de manera que la prioridad más alta siempre esté al principio. El algoritmo para implementar una cola de prioridad usando la lista es el siguiente.
PUSH(HEAD, VALUE, PRIORITY)
Step 1 : Create a new node with VALUE and PRIORITY Step 2
: Check if HEAD has lower priority.If true follow Steps 3 -
4 and end.Else goto Step 5. Step 3 : NEW->NEXT = HEAD Step 4 : HEAD = NEW Step 5
: Set TEMP to head of the list Step 6
: While TEMP->NEXT != NULL and TEMP->NEXT->PRIORITY > PRIORITY Step 7
: TEMP = TEMP->NEXT[END OF LOOP] Step 8 : NEW->NEXT = TEMP->NEXT Step 9
: TEMP->NEXT = NEW Step 10 : End POP(HEAD) Step 2
: Set the head of the list to the next node in the list.HEAD = HEAD->NEXT.Step 3
: Free the node at the head of the list Step 4 : End TOP(HEAD)
: Step 1 : Return HEAD->VALUE Step 2 : End
La operación de inserción agregará elementos a la cola de prioridad de modo que el elemento con la prioridad más alta siempre esté en la parte superior. La operación emergente eliminará el elemento con mayor prioridad de la cola. La operación superior recuperará el elemento de mayor prioridad sin eliminarlo. El programa a continuación muestra cómo podemos empujar, sacar y elementos superiores de una cola de prioridad.
using System;
class PriorityQueue {
public class Node {
public int data;
public int priority;
public Node next;
}
public static Node node = new Node();
public static Node newNode(int d, int p) {
Node temp = new Node();
temp.data = d;
temp.priority = p;
temp.next = null;
return temp;
}
public static int top(Node head) {
return (head).data;
}
public static Node pop(Node head) {
Node temp = head;
(head) = (head).next;
return head;
}
public static Node push(Node head, int d, int p) {
Node start = (head);
Node temp = newNode(d, p);
if ((head).priority > p) {
temp.next = head;
(head) = temp;
} else {
while (start.next != null && start.next.priority < p) {
start = start.next;
}
temp.next = start.next;
start.next = temp;
}
return head;
}
public static int isEmpty(Node head) {
return ((head) == null) ? 1 : 0;
}
public static void Main(string[] args) {
Node queue = newNode(1, 1);
queue = push(queue, 9, 2);
queue = push(queue, 7, 3);
queue = push(queue, 3, 0);
while (isEmpty(queue) == 0) {
Console.Write("{0:D} ", top(queue));
queue = pop(queue);
}
}
}
Producción :
3 1 9 7
El elemento que tiene menos valor de prioridad tiene mayor prioridad.