GATE CSE 1997 | Question: 4.7

Question

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

• A. non-increasing order

• B. non-decreasing order

• C. strictly increasing order

• D. strictly decreasing order

Comments

$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)$

---

In non increasing case , the problem is not when we insert an element(We can push up the newly inserted element if the parent has bigger or equal value), problem starts when we start removing an element from heap, since during heapifying we can’t be sure which of the equal magnitude values entered the Q first without using any additional measure.

---

you can watch this when you doesnot understand suraj kausal solution.All your doubts are clear from here

https://www.youtube.com/watch?v=pNkcCwEwS5I

---

Good question!!

Answer 1

You can find one of the better explaination from here.

https://www.youtube.com/watch?v=pNkcCwEwS5I