Write an algorithm for insertion and deletion in Priority Queues.

Priority queues are a type of abstract data type that are similar to queues, and every item has a priority associated with it. The priority of the elements in a priority queue determines the deletion order.

Let's discuss the algorithms for insertion and deletion operations in a priority queue.

Insertion in Priority Queue

The steps for inserting an element into a priority queue are as follows:

1. Create a new node with the given value.
2. If the priority queue is empty, add the new node as the head of the queue.
3. If the priority queue is not empty, compare the priority of the new node with the nodes in the queue.
4. If the new node has a higher priority (lower priority number), it is placed before the lower priority nodes. If it has a lower priority, it is placed after the higher priority nodes.
5. If two nodes have the same priority, the new node is placed after the existing node.

Here is a pseudo code for insertion:

function insert(queue, node):
    if queue is empty:
        queue = node
    else:
        if node.priority < queue.priority:
            node.next = queue
            queue = node
        else:
            temp = queue
            while temp.next is not None and temp.next.priority <= node.priority:
                temp = temp.next
            node.next = temp.next
            temp.next = node
    return queue

Deletion from Priority Queue

The steps for deleting an element from a priority queue are as follows:

1. Check if the queue is empty. If it is, then there are no elements to delete, return an underflow message.
2. If the queue is not empty, then the node with the highest priority (i.e., the head of the queue) is removed.
3. The next node in the queue becomes the new head of the queue.

Here is a pseudo code for deletion:

function delete(queue):
    if queue is empty:
        return "Underflow"
    else:
        temp = queue
        queue = queue.next
        return temp

In a priority queue, the insertion operation takes place at the end of the queue, so the time complexity is O(n), where n is the number of elements in the queue. The deletion operation takes place at the beginning of the queue, so the time complexity is O(1).