Priority queue implementation provides code to implement priority queue using unordered array. 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 post is using unordered array. In enqueue, the time complexity is O(1). In dequeue, the time complexity is O(n).

Table of Content


Map of priority queue implementations

Part 1 – priority queue implementation – ordered array

you are here


Part 2 – priority queue implementation – unordered 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 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, we have to find the highest priority element first. This requires to exam 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 examing all elements in the array.

Java

Javascript

Python


Print

Print is to print all elements in the array, starting from the index 0 to 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
Download aggregate Data Structures implementations in Java
Download aggregate Data Structures implementations in JavaScript
Download aggregate Data Structures implementations in Python

What are the time complexity of priority queue implementation using array?

pq unordered array

There are two ways to implement with array. The first is to implement as an ordered array. All element are ordered when insert, O(n). To dequeue, remove the last element which has the highest priority, O(1). The second way is to allow new element to enter in an arbitrary unordered array, O(1). To dequeue, find the highest priority element by checking all elements and remove it, O(n).