A priority queue is a queue in which we insert an element at the back (enqueue) and remove an element from the front (dequeue). The element with the highest priority shall be dequeued first. This priority queue implementation provides code to implement a priority queue using an unordered array, in which the time complexity of enqueue is O(1), and that of dequeue is O(n).

priority queue implementation

Table of Content


Map of priority queue implementations

you are here
Part 1 – priority queue implementation – unordered array

Part 2 – priority queue implementation – ordered array
Part 3 – priority queue implementation with heap – iterative solution
Part 4 – priority queue implementation with heap – recursive solution


Enqueue in priority queue implementation

To enqueue an element is the same as adding an element in a regular array -add the element at the next available spot in the array (ie at the end).

Java

Javascript

Python

Doodle

priority queue unordered array


Dequeue

The dequeue operation is to remove the highest priority element from the array. Since the array is not ordered, you have to find the highest priority element first. This requires to examine all elements in the array. Then move the last element in the array to this spot to replace (remove) it. This time complexity is O(n).

Java

Javascript

Python


Peek

Peek is to return the value of the highest priority element. The same as dequeue, we have to find the highest priority element by examining all elements in the array.

Java

Javascript

Python


Print

Print is to print all elements in the array, starting from the index 0 to the highest index. A for loop is used to iterate through each element.

Java

Javascript

Python


Free download

Download priority queue implementation with array in Java, JavaScript and Python
Data structures introduction PDF

How to implement a priority queue using an array?

There are two ways to implement a priority queue using an array. The first is to implement using an ordered array. All elements are sorted during insertion. The second way is to allow new elements to enter using an unordered array. When dequeue, find the highest priority element by checking all elements.