实现一个队列,其中push_rear(),pop_front()和get_min()都是常量时间操作

Question

我遇到了这个问题: 实现一个队列,其中push_rear(),pop_front()和get_min()都是常量时间操作.

我最初想过使用一个最小堆数据结构,它对于get_min()具有O(1)复杂度.但是push_rear()和pop_front()将是O(log(n)).

有谁知道实现这样一个有O(1)push(),pop()和min()的队列的最佳方法是什么？

我搜索了这个,并想指出这个算法极客线程.但似乎没有一个解决方案遵循所有3种方法的恒定时间规则:push(),pop()和min().

感谢所有的建议.

Answer 1

您可以使用O(1)pop(),push()和get_min()实现堆栈:只需将当前最小值与每个元素一起存储.因此,例如,堆栈[4,2,5,1](顶部的1)变为[(4,4), (2,2), (5,2), (1,1)].

然后,您可以使用两个堆栈来实现队列.推到一个堆栈,从另一个堆栈弹出; 如果第二个堆栈在弹出期间为空,则将所有元素从第一个堆栈移动到第二个堆栈.

例如,对于pop请求,从第一个堆栈移动所有元素[(4,4), (2,2), (5,2), (1,1)],第二个堆栈将是[(1,1), (5,1), (2,1), (4,1)].现在返回第二个堆栈的顶部元素.

要查找队列的最小元素,请查看各个最小堆栈的最小两个元素,然后取这两个值中的最小值.(当然,这里有一些额外的逻辑,其中一个堆栈是空的,但这并不难解决).

这将有O(1)get_min()和push()摊销O(1) pop().

Answer 2

好的 - 我想我有一个答案,它给你所有这些操作分摊 O(1),这意味着任何一个操作都可以占用O(n),但任何n个操作序列每个操作需要O(1)时间.

我们的想法是将您的数据存储为笛卡尔树.这是一个遵循min-heap属性的二叉树(每个节点都不比它的子节点大),并且以一种方式排序,使得节点的顺序遍历可以按照添加它们的相同顺序返回节点.例如,这是序列的笛卡尔树2 1 4 3 5:

       1
     /   \
    2      3
          / \
         4   5

可以使用以下过程在O(1)分摊的时间内将元素插入笛卡尔树中.查看树的右侧脊柱(从根部到最右边的叶子的路径始终向右走).从最右边的节点开始,沿着此路径向上扫描,直到找到小于要插入的节点的第一个节点.
更改该节点以使其右子节点成为此新节点,然后将该节点的前右子节点设置为刚刚添加的节点的左子节点.例如,假设我们要在上面的树中插入另一个2的副本.我们沿着右边的脊柱走过5和3,但是因为1 <2而停在1以下.然后我们将树更改为如下所示:

       1
     /   \
    2      2
          /
         3
        / \
       4   5

请注意,inorder遍历给出2 1 4 3 5 2,这是我们添加值的顺序.

这在分摊的O(1)中运行,因为我们可以创建一个等于树右脊中节点数的潜在函数.插入节点所需的实际时间是1加上我们考虑的脊柱中的节点数(称为k).一旦我们找到插入节点的位置,脊柱的大小就会缩短k-1,因为我们访问的每个k节点都不再位于右侧脊柱上,并且新节点就在其位置.对于摊销的O(1)插入,这给出了1 + k +(1-k)= 2 = O(1)的摊销成本.作为另一种思考方式,一旦节点从右侧脊柱移开,它就不再是右侧脊柱的一部分,因此我们将永远不必再次移动它.由于n个节点中的每个节点最多可以移动一次,这意味着n次插入最多可以进行n次移动,因此对于每个元素的摊销O(1),总运行时间最多为O(n).

要执行出列步骤,我们只需从笛卡尔树中删除最左边的节点.如果这个节点是叶子,我们就完成了.否则,节点只能有一个子节点(右子节点),因此我们用其右子节点替换节点.如果我们跟踪最左边节点的位置,则此步骤需要O(1)时间.但是,在删除最左边的节点并将其替换为右子节点后,我们可能不知道新的最左边节点在哪里.为了解决这个问题,我们只需从树的左侧脊柱向下走,从刚刚移动到最左边的子节点的新节点开始.我声称这仍然在O(1)摊销时间内运行.为了看到这一点,我声称在任何一个传递期间最多访问一个节点一次以找到最左边的节点.要看到这一点,请注意,一旦以这种方式访问​​节点,我们再次查看它的唯一方法是将它从最左边节点的子节点移动到最左边的节点.但访问的所有节点都是最左边节点的父节点,因此不会发生这种情况.因此,在此过程中每个节点最多访问一次,并且pop在O(1)中运行.

我们可以在O(1)中做find-min,因为笛卡尔树让我们可以免费访问树中最小的元素; 它是树的根.

最后,要查看节点以与插入它们相同的顺序返回,请注意,笛卡尔树始终存储其元素,以便按顺序遍历以排序顺序访问它们.因为我们总是在每一步删除最左边的节点,这是inorder遍历的第一个元素,所以我们总是按照它们插入的顺序返回节点.

简而言之,我们得到O(1)摊销的推送和流行,以及O(1)最坏情况的发现 - 分钟.

如果我能提出最坏情况的O(1)实现,我肯定会发布它.这是一个很大的问题; 谢谢发帖!

Answer 3

好的,这是一个解决方案.

首先,我们需要一些在0(1)中提供push_back(),push_front(),pop_back()和pop_front()的东西.使用数组和2个迭代器很容易实现.第一个迭代器将指向前,后到后.我们把这种东西称为deque.

这是伪代码:

class MyQueue//Our data structure
{
    deque D;//We need 2 deque objects
    deque Min;

    push(element)//pushing element to MyQueue
    {
        D.push_back(element);
        while(Min.is_not_empty() and Min.back()>element)
             Min.pop_back();
        Min.push_back(element);
    }
    pop()//poping MyQueue
    {
         if(Min.front()==D.front() )
            Min.pop_front();
         D.pop_front();
    }

    min()
    {
         return Min.front();
    }
}

说明:

示例让我们推送数字[12,5,10,7,11,19]和我们的MyQueue

1)推12

D [12]
Min[12]

2)推5

D[12,5]
Min[5] //5>12 so 12 removed

3)推10

D[12,5,10]
Min[5,10]

4)推7

D[12,5,10,7]
Min[5,7]

6)推11

D[12,5,10,7,11]
Min[5,7,11]

7)推19

D[12,5,10,7,11,19]
Min[5,7,11,19]

现在让我们调用pop_front()

我们有

 D[5,10,7,11,19]
 Min[5,7,11,19]

最低为5

我们再次调用pop_front()

说明:pop_front将从D中删除5,但它也会弹出Min的前元素,因为它等于D的前元素(5).

 D[10,7,11,19]
 Min[7,11,19]

最小值是7. :)