‘The blog is my first priority of all!’ It might be true and might not be but what we are concerned about here is the word priority. It is simple in English and in any language meaning putting them first ahead of all. In order to do that we should be aware that why we are having them first. Of course their value! So, in priority, we consider their value (at times) and take decisions. Now, we shall discuss what it has to do with our data structure ‘Priority Queue’.

From the earlier posts, we know what are trees, heap, heapify, and Heapsort. You haven’t read that? Well, you should be first visiting them and continue. All the concepts that will be used are derived from the earlier posts. The links are provided in the section “Reference and Recommendations”. While you are busy reading them, I shall prepare the content for you. ⏳

Priority Queue:

A priority queue is a queue in which the elements are treating according to the values associated with them. In general, the elements with the highest value are considered with the highest priority.

Ex. In a queue of elements 1, 3, 5, 9, and 10; 10 is considered the highest priority element.

Note: If the elements of the same priority occur then they are served with respect to their order in the queue.

The difference between a normal queue and a priority queue is that in a normal queue the principle used is FIFO (First In First Out). But in the priority queue, the elements are served based on their priority.

Implementation:

A priority queue can be implemented using an array, Linked List, Heap, and Binary search tree. The time complexities associated with the operations are given above. Considering the time complexities and implementation technique, the Heap data structure is more efficient. So, we will be using the heap data structure to implement a priority queue here.

Insertion in Priority Queue:

The algorithm is the same as the insertion operation in the heap. Click here to know more.

Algorithm:

1. If there is no node, create a new_node.
2. If there exists a node, insert the new_node at the end i.e. at the end of the array (leaf node from left to right in the tree).
3. Heapify the tree.

The below images illustrate the simple algorithm. For details, visit the article on Heap.

Deletion on Priority Queue:

The algorithm is the same as the deletion operation on the heap. Click here to know more.

Algorithm:

1. Remove the node if the node to be deleted is a leaf node.
2. If it is not the leaf node, swap it with the leaf node and remove the leaf node.
3. Heapify the tree.

The below images illustrate the simple algorithm. For details, visit the article on Heap.

Peek:

This operation returns the maximum or minimum from the queue. It is the root node in the case of max or min-heap.

IMPLEMENTATION IN PYTHON

# Function to heapify the tree
def heapify(arr, n, i):
    # Find the largest among root, left child and right child
    largest = i
    l = 2 * i + 1 #left child of the parent
    r = 2 * i + 2 #right child of the parent

    if l < n and arr[i] < arr[l]:
        largest = l

    if r < n and arr[largest] < arr[r]:
        largest = r

    # Swap and continue heapifying if root is not largest
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)


# Function to insert an element into the tree
def insert(array, newNum):
    size = len(array)
    if size == 0:
        array.append(newNum)
    else:
        array.append(newNum)
        #heapifying after insertion
        for i in range((size // 2) - 1, -1, -1):
            heapify(array, size, i)


# Function to delete an element from the tree
def deleteNode(array, num):
    size = len(array)
    i = 0
    for i in range(0, size):
        if num == array[i]:
            break

    array[i], array[size - 1] = array[size - 1], array[i]

    array.remove(size - 1)
    #heapifying the tree after removing an element
    for i in range((len(array) // 2) - 1, -1, -1):
        heapify(array, len(array), i)
arr = []
#Performing insertion operation
insert(arr, 3)
insert(arr, 6)
insert(arr, 9)
insert(arr, 1)
insert(arr, 2)
insert(arr, 5)
insert(arr, 10)
print ("Max-Heap array: " + str(arr))

#Performing deletion operation
deleteNode(arr, 3)
print("After deleting an element: " + str(arr))

Applications:

1. Implementation of Stack
2. Dijkstra’s algorithm
3. Prim’s Algorithm
4. CPU Scheduling

References and Recommendations:

• Heap Data Structure
• Heap Sort
• Tree Data Structure
• Linked List

Purchase a Dell 3505 Laptop here!

Get Alexa 4th Gen here!