Data Structures - Randomized Queues

Question

I am currently working on the Queues assignment from Princeton's Algorithms Part I. One of the assignments is to implement a randomized queue. This is a question regarding the implementation and tradeoffs of using different data structures.

Question:

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. Create a generic data type RandomizedQueue that implements the following API:

public class RandomizedQueue<Item> implements Iterable<Item> {
    public RandomizedQueue() // construct an empty randomized queue
    public boolean isEmpty() // is the queue empty?
    public int size() // return the number of items on the queue
    public void enqueue(Item item) // add the item
    public Item dequeue() // remove and return a random item
    public Item sample() // return (but do not remove) a random item
    public Iterator<Item> iterator() // return an independent iterator over items in random order
    public static void main(String[] args)   // unit testing
}

The catch here is to implement the dequeue operation and the iterator since the dequeue removes and returns a random element and the iterator iterates over the queue in a random order.

1. Array Implementation:

The primary implementation I was considering is an array implementation. This will be identical to the implementation of an an array queue except the randomness.

Query 1.1: For the dequeue operation, I simply select a number randomly from the size of the array and return that item, and then move the last item in the array to the position of the returned item.

However, this approach changes the order of the queue. In this case it does not matter since I am dequeuing in random order. However, I was wondering if there was an time/memory efficient way to dequeue a random element from the array while preserving the order of the queue without having to create a new array and transfer all the data to it.

// Current code for dequeue - changes the order of the array after dequeue
private int[] queue; // array queue
private int N; // number of items in the queue

public Item dequeue() {
    if (isEmpty()) throw NoSuchElementException("Queue is empty");
    int randomIndex = StdRandom.uniform(N);
    Item temp = queue[randomIndex]        

    if (randomIndex == N - 1) {
        queue[randomIndex] = null; // to avoid loitering
    } else {
        queue[randomIndex] = queue[N - 1];
        queue[randomIndex] = null; 
    }

    // code to resize array

    N--;
    return temp;
}

Query 1.2: For the iterator to meet the requirement of returning elements randomly, I create a new array with all the indices of the queue, then shuffle the array with a Knuth shuffle operation and return the elements at those particular indices in the queue. However, this involves creating a new array equal to the length of the queue. Again, I am sure I am missing a more efficient method.

2. Inner Class Implementation

The second implementation involves an inner node class.

public class RandomizedQueue<Item> {
    private static class Node<Item> {
        Item item;
        Node<Item> next;
        Node<Item> previous;
    }
}

Query 2.1. In this case I understand how to perform the dequeue operation efficiently: Return a random node and change the references for the adjacent nodes.

However, I am confounded by how to return a iterator that returns the nodes in random order without having to create a whole new queue with nodes attached in random order.

Further, what are the benefits of using such a data structure over an array, other than readability and ease of implementation?

This post is kind of long. I appreciate that you guys have taken the time to read my question and help me out. Thanks!

Answer 1

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.

Answer 2

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'

Answer 3

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.

Answer 4

You don't need to shuffle the whole copy of array when you create the iterator, but lazily Fisher-Yate shuffle each element while accessing it in the next() method