Consider an extension of the queue abstract data type, called a minqueue, which supports operations ENQUEUE, DEQUEUE, and FINDMIN. Assume that the elements to be stored are integers (or any other totally ordered data type). FINDMIN simply returns the smallest element in the minqueue, but does not remove it. Using a standard implementation of a queue, the FINDMIN operation takes O(n) time in the worst case. However, consider a more clever data structure for this abstract data type which works as follows: There are two regular queues used. The first queue is called the \'Teal queue\" and the second queue is called the \"helper queue\". When the ENQUEUE(x) operation is performed, the element x is enqueued in the regular way on the real queue. The element x is also enqueued at the end of the helper queue. However, if the element y immediately \"in front\" of x on the helper queue is larger than x, then y is removed from the helper queue. This process of x annihilating the element immediately in front of it is repeated until the clement immediately in front of x Is less than or equal to it or x is at the front of the helper queue. Describe how the DEQUEUE and FINDMIN operation are implemented in this data structure. Give the worst case running time for each of ENQUEUE, DEQUEUE, and FINDMIN using this data structure. Give an argument using the potential method to show that any sequence of n ENQUEUE, DEQUEUE, and FINDMIN operations requires only O(n) time. Or namely, the amortized complexity of these operations is O(1).
a)
FINDMIN: As per the description of the given data structure, the smallest element will always reside on the front of the ‘helper queue’. So FINDMIN just works by:
DEQUEUE:
DEQUEUE works as following:
b)
– moving the element all the way down to helper queue with n comparisons O(n)
So the total time = O(n) + nt, where t is a constant time.
c)
The ENQUEUE operation requires O(n) time and the DEQUEUE and FINDMIN operations require a constant time.
The given structure may be analyzed using the potential function:
= number-of-elements-in-minqueue
This number is always non-negative, as required.
An ENQUEUE operation takes O(n) and increases by 1 and it causes the smallest element to be accessed in constant time
A DEQUEUE operation constant time and also reduces by n, so its amortized time is also constant.
If the In any sequence of n ENQUEUE, DEQUEUE and FINDMIN operations, the total time will be equivalent to O(n).
So the amortized complexity of these operatons is O(n)/n = O(1)
Homework Sourse
