Data Structure: Priority Queue

Priority queues are very frequently used data structures. Used to generate a queue so that we can process the items based on the priority of it.

NOTE

In this article, we are discussing the implementation of Priority Queue in JavaScript and TypeScript.

Check the link below to check the details of Priority Queue-

Priority Queue Details

Here we are using a Max Binary Heap to implement the Priority Queue. The code is mostly the same as Max Binary Heap, there are just a few differences-

Priority Queue using Max Binary Heap

If we represent this Heap(binary tree) in an array, it will look like below-

Notice the indexes of the elements. Here can find the index of child elements from the index of parent, can find parent from the index of children, using the following formula-

• If the parent element is in N th index, then-
  • Left child index: 2N + 1
  • Right child index: 2N + 2
• If the child element is in N th index, then-
  • Parent element index: floor((N – 1) / 2)

Step #1: Node Class

Step #2: Priority Queue Class

Step #3: Enqueue Method

Step #4: Queue Position Setting Utility Method

Define method “setQueuePosition”. This method is used to move an item to the correct position based on the priority.

This function recursively calls itself until all the nodes reach the correct position.

Step #5: Dequeue Method

Full Source Code

Here is the full source code of the Priority Queue implementation-

Demo

Use the following code to check the implementation-

Output:

Here is the output of the demo code-

----------- Priority Queue - Enqueue example -----------

Enqueue - 100| Result Index:  0
Enqueue - 150| Result Index:  0
Enqueue - 80| Result Index:  2
Enqueue - 110| Result Index:  1
Enqueue - 40| Result Index:  4
Enqueue - 120| Result Index:  2
Enqueue - 10| Result Index:  6
Enqueue - 190| Result Index:  0
Enqueue - 55| Result Index:  8
Enqueue - 60| Result Index:  4


----------- Priority Queue - Dequeue example -----------

Dequeue | Result:  Node { data: 'Jamil Bartoletti', priority: 190 }
Dequeue | Result:  Node { data: 'Isaias Hackett', priority: 150 }
Dequeue | Result:  Node { data: 'Candice Braun', priority: 120 }
Dequeue | Result:  Node { data: 'Kali Feil', priority: 110 }
Dequeue | Result:  Node { data: 'Shad Skiles', priority: 100 }
Dequeue | Result:  Node { data: 'Reggie Blick', priority: 80 }
Dequeue | Result:  Node { data: 'Jed Emard', priority: 60 }
Dequeue | Result:  Node { data: 'Laurie Rowe', priority: 55 }
Dequeue | Result:  Node { data: 'Jadyn Lesch', priority: 40 }
Dequeue | Result:  Node { data: 'Bailey Keeling', priority: 10 }
Dequeue | Result:  undefined
Dequeue | Result:  undefined

Testing

Here are the tests for the Priority Queue implementation-

Time Complexity

Source Code

Use the following links to get the source code used in this article-

Source Code of	Implementation Code	Demo Code	Test Code
JavaScript Implementation	GitHub	GitHub	GitHub
TypeScript Implementation	GitHub	GitHub	GitHub

Related Data Structures

Command	Details
Binary Heap	Binary Heap

Other Code Implementations

Use the following links to check the BFS implementation in other programming languages-