# Priority Queue: Array Based Example

Priority Queue is more specialized data structure than a stack or a queue. This article provides an overview about priority queue and array based implementation.

## Priority Queues Introduction:

Priority queue is like an ordinary queue which has a front and a rear and Items are removed from the front. However in this type of queue, items are ordered by key value and the item with the lowest key is always at the front. So the items are inserted in the proper position to maintain the order.

In priority queue, in many instance you access to the element with the lowest key value. So element with smallest key has the highest priority.

Besides providing quick access to the element with smallest key, you also wanted fairly quick insertion. That’s why priority queues are often implemented using data structure called “heap”.

For small numbers of items, or situations in which speed isn’t critical, implementing a priority queue with an array is satisfactory. For larger numbers of items, or when speed is critical, the heap is a better choice.

Now we will learn how to implement priority queue using simple array and later you can learn using heap.

## Priority Queue Example:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
package com.sneppets.dsalgo; class MyPriorityQueue { //max priority queue array size private int maxPQueueArraySize; //priority queue array private long[] myPQueueArray; //number of elements private int nElements; public MyPriorityQueue(int size) { maxPQueueArraySize = size; myPQueueArray = new long[maxPQueueArraySize]; nElements = 0; } //insert element public void insert(long element) { int i; //if there are no elements in the priority queue array if (nElements == 0) { //insert at position 0 myPQueueArray[nElements++] = element; } else { //start at the end for (i=nElements-1; i>=0; i--) { //if the element to be inserted is larger than the element in the queue, //then shift the existing elements upward until you insert the new element at the right place. if(element > myPQueueArray[i]) { //shift existing element up myPQueueArray[i+1] = myPQueueArray[i]; } else //if smaller then shifting is done { break; } } //insert myPQueueArray[i+1] = element; nElements++; } } //remove smallest key element public long remove() { return myPQueueArray[--nElements]; } //peek at smallest key element public long peekSmall() { return myPQueueArray[nElements-1]; } //return true if priority queue is empty public boolean isEmpty() { return (nElements==0); } //return true is priority queue is full public boolean isFull() { return (nElements == maxPQueueArraySize); } } public class PriorityQueueArrayBasedExample { public static void main(String[] args) { MyPriorityQueue myPQ = new MyPriorityQueue(4); //insert 4 elements random in order myPQ.insert(5); myPQ.insert(7); myPQ.insert(3); myPQ.insert(6); while (!myPQ.isEmpty()) { //removing element from priority queue will always remove the smallest element first. long element = myPQ.remove(); System.out.println(element + " "); } } } |

**Output**

1 2 3 4 |
3 5 6 7 |

The insert() method checks whether there are any items; if not, it inserts one at index 0. Otherwise, it starts at the top of the array and shifts existing items upward until it finds the place where the new item should go. Then it inserts the item and increments nItems.

Note that if there’s any chance the priority queue is full, you should check for this possibility with isFull() before using insert(). The front and rear fields are not necessary in priority queue.

## Efficiency of priority queues

Insertion runs in O(n) time. Deletion takes O(1) time. You can improve insertion time with heaps.

## Recommended Posts

- Queue No-count approach and Implementation
- Deque: Double-ended queue is a versatile data structure
- Circular Queue Array Based Implementation
- Queue introduction and implementation in Java
- Reverse a string or word using Stack
- Delimiter Matching using Stack
- Stack Introduction and Implementation in Java

## Leave a Reply