Design a Queue with O(1) lookup time of the Maximum element. You will implement this design using the Array Deque Class in Python.

You will Maintain two Queues - a Main Queue and a Queue holding the Maximum value(s) from the Main Queue (AKA Max Queue).

The Main Queue contains the elements. The Max Queue contains the elements with Maximum value.

The Max Queue would have to be a double ended Queue as you would like to be able to remove elements from both ends 

Transcribed Image Text:

Example: Let's say we have the following: We add an integer 1 into our Main Queue and I hope it is really obvious that when the Main Queue contains a single element, the Max Queue can be popu- lated without confusion :) Main Queue: 1 << front of Queue Max Queue: 1 << front of Queue Now, let's say we insert a 4 into the Main Queue. the Main Queue will look as follows: Main Queue: 4 → 1 << front of Queue In the Max Queue, we don't need 1 anymore, since 1 can never be the Max of this Queue now. So we remove 1 and insert 4. Main Queue: 4 → 1 << front of Queue Max Queue: 4 << front of Queue Say we insert 2 into the Main Queue. We know 2 is not the Max, but it can be the Max if we de-Queue 1 and 4 from the Queue. So, we insert it onto the Max Queue: Main Queue: 2→ 4 → 1 << front of Queue Max Queue: 2→ 4 << front of Queue Further, If we insert a 3 into the Main Queue, we can get rid of the 2 from the Max Queue, because 2 can no longer be the Max of the Queue, even if 4 and 1 are de-Queued. In that case our Queues become: Main Queue: 32 4+1 << front of Queue << front of Queue Max Queue: 3→ 4 In the process of inserting 3, we removed elements from the back of the Max Queue until we found an element > 3. This is because elements < 3 could never be Max after 3 is inserted. What I stated above is exactly the algorithm for inserting an element in the Max Queue. To lookup the Maximum Value (AKA Max), we just check the front of the Max Queue which ensures O(1) lookup time. Example: Let's say we have the following: We add an integer 1 into our Main Queue and I hope it is really obvious that when the Main Queue contains a single element, the Max Queue can be popu- lated without confusion :) Main Queue: 1 << front of Queue Max Queue: 1 << front of Queue Now, let's say we insert a 4 into the Main Queue. the Main Queue will look as follows: Main Queue: 4 → 1 << front of Queue In the Max Queue, we don't need 1 anymore, since 1 can never be the Max of this Queue now. So we remove 1 and insert 4. Main Queue: 4 → 1 << front of Queue Max Queue: 4 << front of Queue Say we insert 2 into the Main Queue. We know 2 is not the Max, but it can be the Max if we de-Queue 1 and 4 from the Queue. So, we insert it onto the Max Queue: Main Queue: 2→ 4 → 1 << front of Queue Max Queue: 2→ 4 << front of Queue Further, If we insert a 3 into the Main Queue, we can get rid of the 2 from the Max Queue, because 2 can no longer be the Max of the Queue, even if 4 and 1 are de-Queued. In that case our Queues become: Main Queue: 32 4+1 << front of Queue << front of Queue Max Queue: 3→ 4 In the process of inserting 3, we removed elements from the back of the Max Queue until we found an element > 3. This is because elements < 3 could never be Max after 3 is inserted. What I stated above is exactly the algorithm for inserting an element in the Max Queue. To lookup the Maximum Value (AKA Max), we just check the front of the Max Queue which ensures O(1) lookup time.

Answer rating: 100% (QA)

I can help you design a queue with O1 lookup time of the maximum element using the array deque class in Python Here are the steps that you need to fol... View the full answer