CODEWITHSUNDEEP
algorithmdata-structuresqueue
user1628340
user1628340

Reputation: 941

Fastest method for Queue Implementation in Java

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.

Upvotes: 1

Views: 1372

Answers (2)

Gene
Gene

Reputation: 46960

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.

Upvotes: 0

amit
amit

Reputation: 178451

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.

Upvotes: 4

Related Questions