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.