a) Bill suggested that he can implement a queue ADT using a priority queue and a
ID: 3731896 • Letter: A
Question
a) Bill suggested that he can implement a queue ADT using a priority queue and a constant amount of additional space. Recall that a queue supports enqueue and dequeue operations, and a priority queue supports min0, removeMin and insert operations. Explain how Bill can achieve this by showing the necessary pseudo code for implementing the queue ADT b) Referring to a) above, what are the tight big-Oh time complexities of the enqueue and dequeue operations of the newly designed queue given that the priority queue is implemented using a heap? Explain your answerExplanation / Answer
To create a queue using priority queue you need to assign priority to the elements that are being enqueue.
Assigning a priority to each element that is being enqueue can act as a priority key to the element. So as you know queue supports enqueue() which inserts element at the front and dequeue() which removes the rear element.
So, lets create a queue with elements stored in form of map (you can use any other data structure as well).
1. Define typedef map<int,int> myMap (in this first int represents element value and secont int represents its priority.)
2. Define functions and priority queue.
int priority; ( priority acts as a key to priority queue)
priority_queue<map<int,int> > p_q;
public:
void enqueue(int n); ()
void dequeue();
int front();
int rear();
bool isEmpty();
};
3. Define enqueue function which increases the priority count and inserts the count with the element value
function enqueue(int n){
priority ++;
p_q.push(myMap(n,priority));
}
4. Define dequeue function which dequeue the element which is by default the one one with the lowest priority as we are increasing priority value while pushing the element and reduces priority count after poping the element.
function dequeue(){
if(p_q.empty()){ cout<<"Nothing to dequeue!!!";}
priority--;
pq.pop();
}
5. return true if queue is empty
function isEmpty(){
return p_q.empty();
}
int main(){
Queue* q=new Queue();
q->push(1);
q->push(2);
q->push(3);
}
This implementation takes O(log n) time for both enqueue and dequeue operations.
This can be slightly optimized by using fibonacci heap implementation of priority queue which would give us O(1) time complexity for enqueue operation, but dequeue still requires O(log n) time.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.