CODEWITHSUNDEEP
algorithm
user4895196
user4895196

Reputation:

How to implement regular queue using priority queue?

How to implement regular queue using priority queue?. Also I need to find the running time of "enqueue" an "dequeue" in this method.

Upvotes: 2

Views: 2796

Answers (2)

Soumik Guha Roy
Soumik Guha Roy

Reputation: 1

Assumptions with respect to Approach 1

  1. K is the key associated with all queue element

  2. K is global variable

  3. Decrease-key(Q,item,K) will decrease the global key value 'K' by 1 and associate the new 'K' value with the 'item'

Approach 1

*ENQUE(Q, item) *

Insert(Q, item) 
Decrease-key(Q, item, K)

DE QUE(Q)

item=Extract-Max(Q)

Approach 2

*ENQUE (Q, ITEM) *

Insert(Q, item) 
Increase-key(Q, item, k)

DE QUE (Q)

Item= Extract-Min(Q)

Running time

  1. Enqueue - O(1)
  2. Dequeue - Log(h) where h is height of the binary heap

NOTE

  1. Approach 1 - K will be monotonic decreasing
  2. Approach 2 - K will be monotonic increasing

Inspired from CLRS book

Upvotes: 0

amit
amit

Reputation: 178521

You can have a running index that remembers how many inserts were made, the ith element that was inserted, will have priority i. You are always polling the "lowest" priority element, which is the oldest one in the queue, as desired.

The time complexity, assuming you are using a "black box" priority queue is O(logn) for popHead() and insert(), and O(1) for top(). You might be able to tweak it to do the insertions and deletions faster if you don't assume "black box", but than again, if you can tweak it - just make it a linked list, or some other data structure that is optimized to be a queue.

Upvotes: 3

Related Questions