Data Structures - Randomized Queues
For your Query 1.1: Here you can indeed remove a random element in constant time. The idea is simply as follows:
- pick a random element to return
- swap it with the last element in your queue
- delete the last element in your queue
This way you keep having a continuous array without 'holes'
In your array implementation, your Query 1.1 seems to be the best way to do things. The only other way to remove a random element would be to move everything up to fill its spot. So if you had [1,2,3,4,5] and you removed 2, your code would move items 3, 4, and 5 up and you'd decrease the count. That will take, on average n/2 item moves for every removal. So removal is O(n). Bad.
If you won't be adding and removing items while iterating, then just use a Fisher-Yates shuffle on the existing array, and start returning items from front to back. There's no reason to make a copy. It really depends on your usage pattern. If you envision adding and removing items from the queue while you're iterating, then things get wonky if you don't make a copy.
With the linked list approach, the random dequeue operation is difficult to implement efficiently because in order to get to a random item, you have to traverse the list from the front. So if you have 100 items in the queue and you want to remove the 85th item, you'll have to start at the front and follow 85 links before you get to the one you want to remove. Since you're using a double-linked list, you could potentially cut that time in half by counting backwards from the end when the item to be removed is beyond the halfway point, but it's still horribly inefficient when the number of items in your queue is large. Imagine removing the 500,000th item from a queue of one million items.
For the random iterator, you can shuffle the linked list in-place before you start iterating. That takes O(n log n) time, but just O(1) extra space. Again, you have the problem of iterating at the same time you're adding or removing. If you want that ability, then you need to make a copy.
Use the array implementation (must be dynamic/resizable) in order to achieve constant (amortized) worst case runtime for all operations except for building the iterator (this takes linear time because of the shuffle).
Here is my implementation:
import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Random;
/* http://coursera.cs.princeton.edu/algs4/assignments/queues.html
*
* A randomized queue is similar to a stack or queue, except that the item
* removed is chosen uniformly at random from items in the data structure.
*/
public class RandomizedQueue<T> implements Iterable<T> {
private int queueEnd = 0; /* index of the end in the queue,
also the number of elements in the queue. */
@SuppressWarnings("unchecked")
private T[] queue = (T[]) new Object[1]; // array representing the queue
private Random rGen = new Random(); // used for generating uniformly random numbers
/**
* Changes the queue size to the specified size.
* @param newSize the new queue size.
*/
private void resize(int newSize) {
System.out.println("Resizing from " + queue.length + " to " + newSize);
T[] newArray = Arrays.copyOfRange(queue, 0, newSize);
queue = newArray;
}
public boolean isEmpty() {
return queueEnd == 0;
}
public int size() {
return queueEnd;
}
/**
* Adds an element to the queue.
* @param elem the new queue entry.
*/
public void enqueue(T elem) {
if (elem == null)
throw new NullPointerException();
if (queueEnd == queue.length)
resize(queue.length*2);
queue[queueEnd++] = elem;
}
/**
* Works in constant (amortized) time.
* @return uniformly random entry from the queue.
*/
public T dequeue() {
if (queueEnd == 0) // can't remove element from empty queue
throw new UnsupportedOperationException();
if (queueEnd <= queue.length/4) // adjusts the array size if less than a quarter of it is used
resize(queue.length/2);
int index = rGen.nextInt(queueEnd); // selects a random index
T returnValue = queue[index]; /* saves the element behind the randomly selected index
which will be returned later */
queue[index] = queue[--queueEnd]; /* fills the hole (randomly selected index is being deleted)
with the last element in the queue */
queue[queueEnd] = null; // avoids loitering
return returnValue;
}
/**
* Returns the value of a random element in the queue, doesn't modify the queue.
* @return random entry of the queue.
*/
public T sample() {
int index = rGen.nextInt(queueEnd); // selects a random index
return queue[index];
}
/*
* Every iteration will (should) return entries in a different order.
*/
private class RanQueueIterator implements Iterator<T> {
private T[] shuffledArray;
private int current = 0;
public RanQueueIterator() {
shuffledArray = queue.clone();
shuffle(shuffledArray);
}
@Override
public boolean hasNext() {
return current < queue.length;
}
@Override
public T next() {
if (!hasNext())
throw new NoSuchElementException();
return shuffledArray[current++];
}
/**
* Rearranges an array of objects in uniformly random order
* (under the assumption that {@code Math.random()} generates independent
* and uniformly distributed numbers between 0 and 1).
* @param array the array to be shuffled
*/
public void shuffle(T[] array) {
int n = array.length;
for (int i = 0; i < n; i++) {
// choose index uniformly in [i, n-1]
int r = i + (int) (Math.random() * (n - i));
T swap = array[r];
array[r] = array[i];
array[i] = swap;
}
}
}
@Override
public Iterator<T> iterator() {
return new RanQueueIterator();
}
public static void main(String[] args) {
RandomizedQueue<Integer> test = new RandomizedQueue<>();
// adding 10 elements
for (int i = 0; i < 10; i++) {
test.enqueue(i);
System.out.println("Added element: " + i);
System.out.println("Current number of elements in queue: " + test.size() + "\n");
}
System.out.print("\nIterator test:\n[");
for (Integer elem: test)
System.out.print(elem + " ");
System.out.println("]\n");
// removing 10 elements
for (int i = 0; i < 10; i++) {
System.out.println("Removed element: " + test.dequeue());
System.out.println("Current number of elements in queue: " + test.size() + "\n");
}
}
}
Note: my implementation is based on the following assignment: http://coursera.cs.princeton.edu/algs4/assignments/queues.html
Bonus challenge: try implementing a toString() method.