Implemente la cola de prioridad usando listas enlazadas.
- push(): esta función se utiliza para insertar nuevos datos en la cola.
- pop(): esta función elimina el elemento con la prioridad más alta de la cola.
- peek() / top(): esta función se usa para obtener el elemento de mayor prioridad en la cola sin eliminarlo de la cola.
Las colas de prioridad se pueden implementar utilizando estructuras de datos comunes como arrays, listas vinculadas, montones y árboles binarios.
Requisitos previos:
listas vinculadas , colas de prioridad
La lista se crea de modo que el elemento de mayor prioridad esté siempre al principio de la lista. La lista está organizada en orden descendente de elementos en función de su prioridad. Esto nos permite eliminar el elemento de mayor prioridad en el tiempo O(1). Para insertar un elemento, debemos recorrer la lista y encontrar la posición adecuada para insertar el Node de modo que se mantenga el orden general de la cola de prioridad. Esto hace que la operación push() tome tiempo O(N). Las operaciones pop() y peek() se realizan en tiempo constante.
Algoritmo:
PUSH(HEAD, DATA, PRIORITY)
Paso 1: Crear un nuevo Node con DATA y PRIORITY
Paso 2: Comprobar si HEAD tiene menor prioridad. Si es verdadero, siga los pasos 3 y 4 y finalice. De lo contrario, vaya al Paso 5.
Paso 3: NUEVO -> SIGUIENTE = CABEZA
Paso 4: CABEZA = NUEVO
Paso 5: Establezca TEMP al principio de la lista
Paso 6: Mientras que TEMP -> SIGUIENTE != NULL y TEMP -> SIGUIENTE -> PRIORIDAD > PRIORIDAD
Paso 7: TEMP = TEMP -> SIGUIENTE
[FIN DEL BUCLE]
Paso 8: NUEVO -> SIGUIENTE = TEMP -> SIGUIENTE
Paso 9: TEMP -> SIGUIENTE = NUEVO
Paso 10: Finalizar
POP(HEAD)
Paso 2: Establecer el cabezal de la lista al siguiente Node de la lista. CABEZA = CABEZA -> SIGUIENTE.
Paso 3: Liberar el Node al principio de la lista
Paso 4: Finalizar
PEEK(HEAD):
Paso 1: Volver HEAD -> DATA
Paso 2: Finalizar
A continuación se muestra la implementación del algoritmo:
C++
// C++ code to implement Priority Queue
// using Linked List
#include <bits/stdc++.h>
using namespace std;
// Node
typedef struct node
{
int data;
// Lower values indicate
// higher priority
int priority;
struct node* next;
} Node;
// Function to create a new node
Node* newNode(int d, int p)
{
Node* temp = (Node*)malloc(sizeof(Node));
temp->data = d;
temp->priority = p;
temp->next = NULL;
return temp;
}
// Return the value at head
int peek(Node** head)
{
return (*head)->data;
}
// Removes the element with the
// highest priority form the list
void pop(Node** head)
{
Node* temp = *head;
(*head) = (*head)->next;
free(temp);
}
// Function to push according to priority
void push(Node** head, int d, int p)
{
Node* start = (*head);
// Create new Node
Node* temp = newNode(d, p);
// Special Case: The head of list has
// lesser priority than new node. So
// insert newnode before head node
// and change head node.
if ((*head)->priority > p)
{
// Insert New Node before head
temp->next = *head;
(*head) = temp;
}
else
{
// Traverse the list and find a
// position to insert new node
while (start->next != NULL &&
start->next->priority < p)
{
start = start->next;
}
// Either at the ends of the list
// or at required position
temp->next = start->next;
start->next = temp;
}
}
// Function to check is list is empty
int isEmpty(Node** head)
{
return (*head) == NULL;
}
// Driver code
int main()
{
// Create a Priority Queue
// 7->4->5->6
Node* pq = newNode(4, 1);
push(&pq, 5, 2);
push(&pq, 6, 3);
push(&pq, 7, 0);
while (!isEmpty(&pq))
{
cout << " " << peek(&pq);
pop(&pq);
}
return 0;
}
// This code is contributed by shivanisinghss2110
C
// C code to implement Priority Queue
// using Linked List
#include <stdio.h>
#include <stdlib.h>
// Node
typedef struct node {
int data;
// Lower values indicate higher priority
int priority;
struct node* next;
} Node;
// Function to Create A New Node
Node* newNode(int d, int p)
{
Node* temp = (Node*)malloc(sizeof(Node));
temp->data = d;
temp->priority = p;
temp->next = NULL;
return temp;
}
// Return the value at head
int peek(Node** head)
{
return (*head)->data;
}
// Removes the element with the
// highest priority form the list
void pop(Node** head)
{
Node* temp = *head;
(*head) = (*head)->next;
free(temp);
}
// Function to push according to priority
void push(Node** head, int d, int p)
{
Node* start = (*head);
// Create new Node
Node* temp = newNode(d, p);
// Special Case: The head of list has lesser
// priority than new node. So insert new
// node before head node and change head node.
if ((*head)->priority > p) {
// Insert New Node before head
temp->next = *head;
(*head) = temp;
}
else {
// Traverse the list and find a
// position to insert new node
while (start->next != NULL &&
start->next->priority < p) {
start = start->next;
}
// Either at the ends of the list
// or at required position
temp->next = start->next;
start->next = temp;
}
}
// Function to check is list is empty
int isEmpty(Node** head)
{
return (*head) == NULL;
}
// Driver code
int main()
{
// Create a Priority Queue
// 7->4->5->6
Node* pq = newNode(4, 1);
push(&pq, 5, 2);
push(&pq, 6, 3);
push(&pq, 7, 0);
while (!isEmpty(&pq)) {
printf("%d ", peek(&pq));
pop(&pq);
}
return 0;
}
Java
// Java code to implement Priority Queue
// using Linked List
import java.util.* ;
class Solution
{
// Node
static class Node {
int data;
// Lower values indicate higher priority
int priority;
Node next;
}
static Node node = new Node();
// Function to Create A New Node
static Node newNode(int d, int p)
{
Node temp = new Node();
temp.data = d;
temp.priority = p;
temp.next = null;
return temp;
}
// Return the value at head
static int peek(Node head)
{
return (head).data;
}
// Removes the element with the
// highest priority form the list
static Node pop(Node head)
{
Node temp = head;
(head) = (head).next;
return head;
}
// Function to push according to priority
static Node push(Node head, int d, int p)
{
Node start = (head);
// Create new Node
Node temp = newNode(d, p);
// Special Case: The head of list has lesser
// priority than new node. So insert new
// node before head node and change head node.
if ((head).priority > p) {
// Insert New Node before head
temp.next = head;
(head) = temp;
}
else {
// Traverse the list and find a
// position to insert new node
while (start.next != null &&
start.next.priority < p) {
start = start.next;
}
// Either at the ends of the list
// or at required position
temp.next = start.next;
start.next = temp;
}
return head;
}
// Function to check is list is empty
static int isEmpty(Node head)
{
return ((head) == null)?1:0;
}
// Driver code
public static void main(String args[])
{
// Create a Priority Queue
// 7.4.5.6
Node pq = newNode(4, 1);
pq =push(pq, 5, 2);
pq =push(pq, 6, 3);
pq =push(pq, 7, 0);
while (isEmpty(pq)==0) {
System.out.printf("%d ", peek(pq));
pq=pop(pq);
}
}
}
// This code is contributed
// by Arnab Kundu
Python3
# Python3 code to implement Priority Queue # using Singly Linked List # Class to create new node which includes # Node Data, and Node Priority class PriorityQueueNode: def __init__(self, value, pr): self.data = value self.priority = pr self.next = None # Implementation of Priority Queue class PriorityQueue: def __init__(self): self.front = None # Method to check Priority Queue is Empty # or not if Empty then it will return True # Otherwise False def isEmpty(self): return True if self.front == None else False # Method to add items in Priority Queue # According to their priority value def push(self, value, priority): # Condition check for checking Priority # Queue is empty or not if self.isEmpty() == True: # Creating a new node and assigning # it to class variable self.front = PriorityQueueNode(value, priority) # Returning 1 for successful execution return 1 else: # Special condition check to see that # first node priority value if self.front.priority > priority: # Creating a new node newNode = PriorityQueueNode(value, priority) # Updating the new node next value newNode.next = self.front # Assigning it to self.front self.front = newNode # Returning 1 for successful execution return 1 else: # Traversing through Queue until it # finds the next smaller priority node temp = self.front while temp.next: # If same priority node found then current # node will come after previous node if priority <= temp.next.priority: break temp = temp.next newNode = PriorityQueueNode(value, priority) newNode.next = temp.next temp.next = newNode # Returning 1 for successful execution return 1 # Method to remove high priority item # from the Priority Queue def pop(self): # Condition check for checking # Priority Queue is empty or not if self.isEmpty() == True: return else: # Removing high priority node from # Priority Queue, and updating front # with next node self.front = self.front.next return 1 # Method to return high priority node # value Not removing it def peek(self): # Condition check for checking Priority # Queue is empty or not if self.isEmpty() == True: return else: return self.front.data # Method to Traverse through Priority # Queue def traverse(self): # Condition check for checking Priority # Queue is empty or not if self.isEmpty() == True: return "Queue is Empty!" else: temp = self.front while temp: print(temp.data, end = " ") temp = temp.next # Driver code if __name__ == "__main__": # Creating an instance of Priority # Queue, and adding values # 7 -> 4 -> 5 -> 6 pq = PriorityQueue() pq.push(4, 1) pq.push(5, 2) pq.push(6, 3) pq.push(7, 0) # Traversing through Priority Queue pq.traverse() # Removing highest Priority item # for priority queue pq.pop() # This code is contributed by himanshu kanojiya
C#
// C# code to implement Priority Queue
// using Linked List
using System;
class GFG
{
// Node
public class Node
{
public int data;
// Lower values indicate
// higher priority
public int priority;
public Node next;
}
public static Node node = new Node();
// Function to Create A 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;
}
// Return the value at head
public static int peek(Node head)
{
return (head).data;
}
// Removes the element with the
// highest priority form the list
public static Node pop(Node head)
{
Node temp = head;
(head) = (head).next;
return head;
}
// Function to push according to priority
public static Node push(Node head,
int d, int p)
{
Node start = (head);
// Create new Node
Node temp = newNode(d, p);
// Special Case: The head of list
// has lesser priority than new node.
// So insert new node before head node
// and change head node.
if ((head).priority > p)
{
// Insert New Node before head
temp.next = head;
(head) = temp;
}
else
{
// Traverse the list and find a
// position to insert new node
while (start.next != null &&
start.next.priority < p)
{
start = start.next;
}
// Either at the ends of the list
// or at required position
temp.next = start.next;
start.next = temp;
}
return head;
}
// Function to check is list is empty
public static int isEmpty(Node head)
{
return ((head) == null) ? 1 : 0;
}
// Driver code
public static void Main(string[] args)
{
// Create a Priority Queue
// 7.4.5.6
Node pq = newNode(4, 1);
pq = push(pq, 5, 2);
pq = push(pq, 6, 3);
pq = push(pq, 7, 0);
while (isEmpty(pq) == 0)
{
Console.Write("{0:D} ", peek(pq));
pq = pop(pq);
}
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// JavaScript code to implement Priority Queue
// using Linked List
// Node
class Node
{
// Lower values indicate
// higher priority
constructor() {
this.data = 0;
this.priority = 0;
this.next = null;
}
}
var node = new Node();
// Function to Create A New Node
function newNode(d, p) {
var temp = new Node();
temp.data = d;
temp.priority = p;
temp.next = null;
return temp;
}
// Return the value at head
function peek(head) {
return head.data;
}
// Removes the element with the
// highest priority form the list
function pop(head) {
var temp = head;
head = head.next;
return head;
}
// Function to push according to priority
function push(head, d, p) {
var start = head;
// Create new Node
var temp = newNode(d, p);
// Special Case: The head of list
// has lesser priority than new node.
// So insert new node before head node
// and change head node.
if (head.priority > p)
{
// Insert New Node before head
temp.next = head;
head = temp;
}
else
{
// Traverse the list and find a
// position to insert new node
while (start.next != null && start.next.priority < p) {
start = start.next;
}
// Either at the ends of the list
// or at required position
temp.next = start.next;
start.next = temp;
}
return head;
}
// Function to check is list is empty
function isEmpty(head) {
return head == null ? 1 : 0;
}
// Driver code
// Create a Priority Queue
// 7.4.5.6
var pq = newNode(4, 1);
pq = push(pq, 5, 2);
pq = push(pq, 6, 3);
pq = push(pq, 7, 0);
while (isEmpty(pq) == 0) {
document.write(peek(pq) + " ");
pq = pop(pq);
}
// This code is contributed by rdtank.
</script>
Producción:
7 4 5 6
Complejidades de tiempo y comparación con Binary Heap :
peek() push() pop()
-----------------------------------------
Linked List | O(1) O(n) O(1)
|
Binary Heap | O(1) O(Log n) O(Log n)
Publicación traducida automáticamente
Artículo escrito por Sayan Mahapatra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA