A priority queue is an abstract data type which is like a regular queue, but where additionally each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority. In some implementations, if two elements have the same priority, they are served according to the order in which they were enqueued, while in other implementations, ordering of elements with the same priority is undefined.

A priority queue must at least support the following operations:

• CreateQueue to create a priority queue
• EnQueue according to a priority
• DeQueue the front element (highest priority)
• Check the Front element
• isEmptyQueue to check if the priority queue is empty
• update_priority for a given element

Implement a priority queue using a linked list

#include<stdlib.h>
#include<stdio.h>

#define N 20
typedef int element;
struct cell { 
	element data; 
	int priority;
	struct cell *next; 
};

typedef  struct { 
	struct cell *front; 
} queue;

queue CreateQueue()
{
	queue q;
	q.front = NULL;
	return q;
}

int isEmptyQueue(queue q)
{
	return q.front == NULL;
}

int Front(queue q, element *e)
{
	if (isEmptyQueue(q)) return 0;
	*e = q.front->data;
	return 1;
}


int DeQueue(queue *q)
{
	struct cell *temp;
	if (isEmptyQueue(*q)) return 0;
	temp = q->front;
	q->front = q->front->next;
	free(temp);
	return 1;
}


void display_queue(queue tmp)
{
	struct cell *temp = tmp.front;

	if (temp == NULL)
		printf("Queue is empty\n");
	else
	{
		printf("Queue is :\n");
		printf("Item\n");
		while (temp != NULL)
		{
			printf("%5d         %5d\n\n", temp->priority, temp->data);
			temp = temp->next;
		}
	}
}

int EnQueue(queue *q, element e, int priority)
{
	struct cell *temp, *href;
	temp = (struct cell *) malloc(sizeof(struct cell));
	if (!temp) return 0;
	temp->data = e;
	temp->priority = priority;

	if (q->front == NULL || priority < q->front->priority) {/*Queue is empty or item to be added has priority more than first item*/
		temp->next = q->front;
		q->front = temp;
	}
	else
	{
		href = q->front;
		while (href->next != NULL && href->next->priority <= priority)
			href = href->next;
		temp->next = href->next;
		href->next = temp;
	}

	return 1;
}

void delete_head(struct cell **nodeRef)
{
	struct cell *p;
	p = *nodeRef;
	*nodeRef = (*nodeRef)->next;
	free(p);
}

// delete a given element (recursive)
int delete_value(struct cell **nodeRef, element e)
{
	if (*nodeRef == NULL)
		return 0;
	if ((*nodeRef)->data == e)
	{
		delete_head(nodeRef);
		return 1;
	}
	return delete_value(&((*nodeRef)->next), e);
}


void recursive_ordered_insert(struct cell **node, element value, int priority)
{
	struct cell *temp;
	if ((*node == NULL) || !((*node)->priority <= priority))
	{
		temp = *node;
		*node = (struct cell *) malloc(sizeof(struct cell));
		if (!*node) return ;
		(*node)->data = value;
		(*node)->priority = priority;
		(*node)->next = temp;
		return;
	}

	 recursive_ordered_insert(&((*node)->next), value, priority);

}


void update_priority(queue *q, element data, int priority) {
	if (delete_value(&(q->front), data) == 1)
		recursive_ordered_insert(&(q->front), data, priority);
	// or	EnQueue(q, data, priority);
	
}

int main()
{
    queue q;
    q=CreateQueue();
    
    
    EnQueue(&q, 10, 2);
    display_queue(q);
    EnQueue(&q, 11, 4);
    display_queue(q);
    EnQueue(&q, 12, 3);
    display_queue(q);
    EnQueue(&q, 122, 3);
    display_queue(q);
    update_priority(&q, 122, 2) ;
    display_queue(q);  
    
    return 0;

}