5.8k views

A priority queue $Q$ is used to implement a stack that stores characters. PUSH (C) is implemented as INSERT $(Q, C, K)$ where $K$ is an appropriate integer key chosen by the implementation. POP is implemented as DELETEMIN$(Q)$. For a sequence of operations, the keys chosen are in

1. non-increasing order

2. non-decreasing order

3. strictly increasing order

4. strictly decreasing order

in DS
edited | 5.8k views
+2

$Values: 1,1,2,3,4$

$Priority(K):1(5),1(4),2(3),3(2),4(1)$

 $4$$(1) 3$$(2)$ $2$$(3) 1$$(4)$ $1$$(5)$

$\fbox{STACK}$

We need to choose keys in striclty decreasing order in order to satify $STACK$ property as well as $DELETE-MIN(Q)$

Implementing stack using priority queue require first element inserted in stack will be deleted at last, and to implement it using deletemin() operation of queue will require first element inserted in queue must have highest priority.

So the keys must be in strictly decreasing order.

Correct Answer: $D$

edited
0

@srestha mam priority of element doesn't depend always on the value of the element but the right thing is it depends on the priority of the element that's the reason it is known as a priority queue.

A binary tree that stores priorities (Or priority element) pairs at nodes

In your case, you have taken min-heap, but before that please look at what is given insert function

PUSH (C) is implemented as INSERT (Q,C,K) where K is an appropriate integer key chosen by the implementation.

Clearly, we can see here node is taken as pair. So a node is taken as pairs <element, K(priority)> and min-heap finds out not by the element of a node but by priority of that node.

And Coming to the question:

Then why it is named DELETEMIN()??

It is delete-min because it finds the minimum value of priority not the minimum value of an element, here case is different

See this Nptel video for a clear idea:

+1

Was I saying correct ? If no what was the error.

+1

Yes @Satbir

0

they are asking for a sequence of operation, that means

i) In time of pushing, they are using "strictly decreasing order sequence" or

II)at the time of popping. they using "strictly decreasing order sequence"??

Another thing

DeleteMin(Q) actually deleting priority-wise-minimum key. right??

So, it has disadvantage of deletion of O(n) time. rt??

0
at the time of pushing
0

0

@srestha mam have you seen the video

0
why not popping??
0
because it is operating on key not element
0
yes, video is about priority queue, but this question is an implementation of priority queue.
0

@srestha mam i have shared with timing please check that once

0
what timing??
0

just play the video given above @srestha mam

0
I have heard this lecture.
0

there clearly mentioned

the nodes as containing the priority of the element and the element is sitting somewhere here also.

0
...
0

@srestha mam if still, your doubt is not clear then this will clear  So D is the correct option no doubt about that

CLRS Book page:163-164

0

I cannot agree with u still now.

Even see here , they are also disagree why key will be stricly decreasing https://stackoverflow.com/questions/35043596/how-to-implement-a-stack-using-a-priority-queue

(A) non-increasing order can not be true because two same (identical) numbers can not have same priority as priority should be distinguishable for each number.

So, option A) canceled.

Now ,

As given “POP is implemented as DELETEMIN(Q)” that means Stack returns minimum element always.

and  according to stack overflow,

Priority queue, maintain heap property. According to this elements must be ordered

So, elements either return max-heap or min-heap. And for this not unsorted elements will be allowed here.  And as we delete minimum element first, So, insertion of element must be decreasing order.

@Satbir

priority queue nothing but heap here.In ur diagram is it maintaining heap property??

https://www.geeksforgeeks.org/gate-gate-cs-1997-question-32/

I hope all doubt now gone for this question.

+1

@srestha,

He has given you the link to the NPTEL video, CLRS what more do you want ?

I Don't want to discuss it anymore.

0
............
Here we need to implement stack .

For it last element inserted must be poped  first.

Priority Q can be implemented by min heap or max heap but here priority Q operation is given deleteMin that means in the sense of stack minimum element having the higher priority that means here we are talking about min heap .

Means first element of heap should be lastly inserted that means keys must be inserted in decreasing order.

Since it is priority Q and two element doesn't have same priority so strictly decreasing order.
0
One doubt key can be 1 1 2 3 4(As there not mentioned repeated element not allowed)

So, in that case is not the answer will be A) means ans simply be non increasing order
0

in the queue the elements are present in the following manner:-

1 | 2 | 3 | 4 | 5

now rear will point to 1 and front will point to 5, according to the rule of queue then it delete 5.

but how deletemin () is deleting the elements from rear??

0
I have drawn it in fig

If figure has any problem?
0

Hi papesh, A priority queue Q is used to implement a stack. It means we are going to perform operations on a priority queue to simulate it like a stack. As we require deletemin(), going for min-heap is a better choice.

Lets say sequence is in increasing order, and we are implementing a min-heap using an array. Let the elements be 1,2,3,4,5,6,7. This key arrangement is already in a min heap format and it will simulate stack where pop operation deletes minimum element. Now even if add one element lets say 8, it will go to end of the array and while popping its still going to pop minimum element. So the overall arrangement is increasing order.

but the answer says it should be in strictly decreasing order. What should have been the correct way of solving it and where am I making mistake?

"Means first element of heap should be lastly inserted that means keys must be inserted in decreasing order."  Also I am not clear with this statement.

0

@srestha mam elements can be in non-increasing order but keys K should be in strictly decreasing order

0
What is difference between elements and key, I havenot got.
0
.......
0
............
0
you mean priority of element as key, that represents as k here.

right??

But, if value(represent by C) is non increasing order, then priority also can be non-increasing order.
0
priority can not be in non-increasing order
0

see this

void Stack::push(int n){
cnt++;
pq.push(pi(cnt, n));
}

Is there any possiblity cnt have same value while insertion

0
counting element of stack and pushing element such that element delete min element from stack first, are not same thing.

right?
0
delete min is deleting that element which has minimum priority not the minimum value
0

srestha mam see this https://www.geeksforgeeks.org/implement-stack-using-priority-queue-or-heap/  code here and there typedef pair<int, int> pi; is used it means value and priority have taken seperately

0

In ans , what is meaning of this line?

queue will require first element inserted in queue must have highest priority.

0
..........
+1

U have taken  Rear element as lowest priority. But , they have taken it as highest priority

0

@srestha mam

they have taken first element as highest priority (front point here) it means element at rear will be lowest priority there too

0
first element inserted in queue must have highest priority. see selected answer @srestha mam
+1

tell me this

When we implement queue to implement a stack, We need atleast 2 queue.

But here we implementing with one priority queue. Now if we  insert 1,1,2,3,4  then according to stack it should remove 4,3,2,1,1

right??

Then how min delete first?? 4 will remove first according to stack.

Secondly according to ur dia, if $4$ remove first, then lowest priority element will remove first. That means priority comes in min-delete 1,2,3,4,5 , which will be an increasing order.

right??

0

@srestha mam INSERT $(Q,C,K)$ where $K$ is an appropriate integer key chosen by the implementation.

0 @srestha mam check this insertion by decrementing key(k) and deletion by incrementing the index(key k)

0
That is not maintaining stack property then.  Because in stack which inserted last should remove first
0

@srestha yes mam diagram was wrong

0

Have u got correct diagram for it?? Though ur logic is valid I think.

0

I think priority queue implementation is nothing but 'Min-heap' implementation. So, if we insert values like 5,4,3,2,1 it always give 1,2,3,4,5 as output. right??

So, you mentioned priority separately, but that is not needed. right??

But one thing, if priority queue takes max heap as representation , then D) will not be answer. right?? So, what about max-heap??

0

@srestha

Yes mam you are right,

option A vs option D

https://en.wikipedia.org/wiki/Priority_queue

In a stack, the priority of each inserted element is monotonically increasing; thus, the last element inserted is always the first retrieved. In a queue, the priority of each inserted element is monotonically decreasing; thus, the first element inserted is always the first retrieved.

Explanation :- A priority queue works on the bases of it's element's priority , it doesn't do operation in FIFO or LIFO manner like normal queue and stack do. Like here we defined some operation like DELETEMIN(Q) , so this abstract  data structure will help to delete minimum priority element from priority queue , noe it doesn't matter in which order the element are inserted.

like if elements are like 5,3,2,7,8 DELETEMIN(Q) will delete 2 (see no FIFO).We have to here implement stack using Priority queue (although practically it's not a good approach to implement stack using priority queue)so here element must follow LIFO mechanism. Now if elements are in strictly decreasing order we can implement stack using priority queue successfully but when elements are repeated (non-increasing order) then our priority queue will behave like a normal queue and it will follow FIFO approach but to implement stack element  have to follow LIFO approach , which won't be possible.

elements : $3_{a} , 3_{b},3_{c},3_{d}$    // all elements are same , to take care about order of insertion i named them like $3_{a} , 3_{b}$ and so on...

Here i'm taking the help of https://www.geeksforgeeks.org/implement-stack-using-priority-queue-or-heap/

to implement stack using priority queue. the key concept is add a count to each variable which will indicate when the element was inserted (think like time)

$3_{a}$ is pushed into stack at t=1

$3_{b}$  is pushed into stack at t=2

$3_{c}$ is pushed into stack at t=3

$3_{d}$ is pushed into stack at t=4

we implement PUSH as

push_stack(data)

{

t++;

PQ.push(pair(t,data));

}

So stack is like

 $3_{d}$    (t=4) $3_{c}$    (t=3) $3_{b}$    (t=2) $3_{a}$    (t=1)

We implement POP as

pop_stack(data)

{

t--;

PQ.pop();

}

So we can see the first element the PQ.pop() will pop is on the bases on FIFO order and it would be $3_{a}$  but it's not what stack will pop (stack would have to follow LIFO so it would have to pop $3_{d}$)  so that's why option A would be false.

0
which can be an appropriate text book to refer such topics of data structure?

In CLRS, its not mentioned in depth, if I am not wrong. Please someone suggest !