1

The task is to implement a queue in java with the following methods:

  1. enqueue //add an element to queue
  2. dequeue //remove element from queue
  3. peekMedian //find median
  4. peekMinimum //find minimum
  5. peakMaximum //find maximum
  6. size // get size

Assume that ALL METHODS ARE CALLED In EQUAL FREQUENCY, the task is to have the fastest implementation.

My Current Approach: Maintain a sorted array, in addition to the queue, so enqueue and dequeue are take O(logn) and peekMedian, peekMaximum, peekMinimum all take O(1) time.

Please suggest a method that will be faster, assuming all methods are called in equal frequency.

Improve this question
1
  • maintain sorted array is O(n) per insertion/deletion (worst case) Commented Jan 16, 2013 at 16:38

2 Answers 2

Reset to default
4

Well, you are close - but there is still something missing, since inserting/deleting from a sorted array is O(n) (because at probability 1/2 the inserted element is at the first half of the array, and you will have to shift to the right all the following elements, and there are at least n/2 of these, so total complexity of this operation is O(n) on average + worst case)

However, if you switch your sorted DS to a skip list/ balanced BST - you are going to get O(logn) insertion/deletion and O(1) minimum/maximum/median/size (with caching)

EDIT:

You cannot get better then O(logN) for insertion (unless you decrease the peekMedian() to Omega(logN)), because that will enable you to sort better then O(NlogN):

First, note that the median moves one element to the right for each "high" elements you insert (in here, high means >= the current max).
So, by iteratively doing:

while peekMedian() != MAX:
   peekMedian()
   insert(MAX)
   insert(MAX)

you can find the "higher" half of the sorted array.
Using the same approach with insert(MIN) you can get the lowest half of the array.

Assuming you have o(logN) (small o notation, better then Theta(logN) insertion and O(1) peekMedian(), you got yourself a sort better then O(NlogN), but sorting is Omega(NlogN) problem.
=><=

Thus insert() cannot be better then O(logN), with median still being O(1).

QED

EDIT2: Modifying the median in insertions:

If the tree size before insertion is 2n+1 (odd) then the old median is at index n+1, and the new median is at the same index (n+1), so if the element was added before the old median - you need to get the preceding node of the last median - and that's the new median. If it was added after it - do nothing, the old median is the new one as well.

If the list is even (2n elements), then after the insertion, you should increase an index (from n to n+1), so if the new element was added before the median - do nothing, if it was added after the old median, you need to set the new median as the following node from the old median.

note: In here next nodes and preceding nodes are those that follow according to the key, and index means the "place" of the node (smallest is 1st and biggest is last).
I only explained how to do it for insertion, the same ideas hold for deletion.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

@amit- on maintaining an additional BST, how can we get median in constant time?
@user1628340 Caching. It is very simple to maintain it while inserting/deleting - and it is still within the O(logN) of insertion/deletion
@amit-I am not really aware of caching. Please elaborate.
@user1628340 Whenever you insert/delete an element - find the new median - and store it in a variable called median, when you ask for median - you just need to retrieve it. There are some optimizations you can make - but none improve the asymptotic time complexity - so I'd ignore them for now.
@amit- how can you find median from a bst in O(logn) ?
|
0

There is a simpler and perhaps better solution. (As has been discussed, the sorted array makes enqueue and dequeue both O(n), which is not so good.)

Maintain two sorted sets in addition to the queue. The Java library provides e.g. SortedSet, which are balanced search trees. The "low set" stores the first ceiling (n/2) elements in sorted order. The second "high set" has the last floor(n/2).

NB: If duplicates are allowed, you'll have to use something like Google's TreeMultiset instead of regular Java sorted sets.

To enqueue, just add to the queue and the correct set. If necessary, re-establish balance between the sets by moving one element: either the greatest element in the low set to the upper set or the least element in the high set to the low. Dequeuing needs the same re-balance operation.

Finding the median if n is odd is just looking up the max element in the low set. If n is even, find the max element in the low set and min in the high set and average them.

With the native Java sorted set implementation (balanced tree), this will be O(log n) for all operations. It will be very easy to code. About 60 lines.

If you implement your own sifting heaps for the low and high sets, then you'll have O(1) for the find median operation while all other ops will remain O(log n).

If you go on and implement your own Fibonacci heaps for the low and high sets, then you'll have O(1) insert as well.

Improve this answer

2 Comments

@gene- Set does not allow duplicate values, while a queue allows it! Can you think of any efficient data structure allowing duplicate values?
True. I added a remark labeled NB above. You need multisets to handle duplicates. Happily Google provides these in their Collections library...

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.