priority queue

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:


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


Leave a Reply

Notify of