数据结构 - 随机队列

Question

我目前正在研究普林斯顿的算法第一部分.其中一项任务是实现一个随机队列.这是关于使用不同数据结构的实现和权衡的问题.

题:

随机队列类似于堆栈或队列,除了从数据结构中的项目随机均匀地选择移除的项目.创建实现以下API的通用数据类型RandomizedQueue:

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
}

这里的问题是实现dequeue操作和迭代器,因为dequeue删除并返回一个随机元素,迭代器以随机顺序迭代队列.

1.阵列实施:

我正在考虑的主要实现是数组实现.这与除随机性之外的阵列队列的实现相同.

查询1.1:对于出列操作,我只是从数组的大小中随机选择一个数字并返回该项,然后将数组中的最后一项移动到返回项的位置.

但是,此方法会更改队列的顺序.在这种情况下,无关紧要,因为我以随机顺序出列.但是,我想知道是否有时间/内存有效的方法从阵列中出现一个随机元素,同时保留队列的顺序,而不必创建一个新的数组并将所有数据传输给它.

// 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;
}

查询1.2:为了使迭代器满足随机返回元素的要求,我创建了一个包含队列所有索引的新数组,然后使用Knuth shuffle操作对数组进行洗牌,并返回队列中这些特定索引处的元素.但是,这涉及创建一个等于队列长度的新数组.再说一遍,我确信我错过了一种更有效的方法.

2.内部类实现

第二个实现涉及内部节点类.

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

查询2.1.在这种情况下,我了解如何有效地执行出队操作:返回随机节点并更改相邻节点的引用.

但是,我对如何返回一个迭代器感到困惑,该迭代器以随机顺序返回节点,而不必创建一个以随机顺序连接节点的整个新队列.

此外,除了可读性和易于实现之外,在阵列上使用这种数据结构有什么好处？

这篇文章有点长.我感谢你们花时间阅读我的问题并帮助我.谢谢!

Answer 1

在您的数组实现中,您的Query 1.1似乎是最好的方法.删除随机元素的唯一方法是将所有内容移动以填充其位置.因此,如果你已经[1,2,3,4,5]删除了2,你的代码会移动第3,4和5项,你就会减少计数.每次移除平均需要n/2项移动.所以删除是O(n).坏.

如果在迭代时不添加和删除项目,则只需在现有数组上使用Fisher-Yates shuffle,然后开始从前向后返回项目.没有理由复制.这实际上取决于您的使用模式.如果您想要在迭代时从队列中添加和删除项目,那么如果您不进行复制,则会出现问题.

使用链表方法,随机出列操作难以有效实现,因为为了获得随机项,您必须从前面遍历列表.因此,如果队列中有100个项目,并且您想要删除第85个项目,则必须先从前面开始并按照85个链接开始,然后再转到要删除的项目.由于您使用的是双链表,因此当您要删除的项目超出中途点时,可以通过从结尾向后计数来缩短一半的时间,但是当队列中的项目数量仍然非常低效时很大.想象一下,从一百万个项目的队列中删除第500,000个项目.

对于随机迭代器,您可以在开始迭代之前就地对链接列表进行随机播放.这需要O(n log n)时间,但只需要O(1)额外空间.同样,您在添加或删除的同时遇到迭代问题.如果你想要那种能力,那么你需要复制一份.

Answer 2

对于您的查询 1.1：在这里您确实可以在恒定时间内删除随机元素。思路很简单：

• 选择一个随机元素返回
• 与队列中的最后一个元素交换它
• 删除队列中的最后一个元素

这样你就可以拥有一个没有“洞”的连续数组