如何在 O(1) 时间内将列表中的最后一项移到最前面？

Question

我的代码是这样的，其中 heap 是 list:

 heap[0] = heap.pop()

问题是弹出唯一项时它不起作用。根据 python wiki，弹出最后一个元素是 O(1)。（我也想去掉最后一个元素）

到目前为止我已经想出了：

last_element = heap.pop()  # I don't want to catch potential IndexError here
try:
    heap[0] = last_element
except IndexError:
    heap.append(last_element)

长很多

或这个

if len(heap) != 1:
    heap[0] = heap.pop()

哪个应该更慢。

是否有更 pythonic 的方法来做到这一点？在内部 python 可能甚至不调整数组的大小。

更新：我需要 O(1) 访问给定索引处的元素（因此它不能是链表）。

Answer 1

collections.deque 支持在 O(1) 的前面和后面删除和附加。

参见https://wiki.python.org/moin/TimeComplexity。

Answer 2

您可以在尝试弹出之前检查列表是否为空。

if len(a) > 0:
  a.insert(0,a.pop())

默认情况下，从列表中弹出 returns 最后一个元素，因此您不必显式传递 -1。因为如果列表为空它会引发错误，我们可以在尝试弹出之前检查它的长度。

但是列表的插入操作是 O(n)。对于 O(1)，您将需要使用出列。

from collections import deque
a = deque()
a.append(10)
a.append(12)
if len(a) > 0:
  a.appendleft(a.pop())
print a

Answer 3

听起来你在实现堆，这一行是堆弹出操作实现的一部分。在上下文中，它看起来像

def heappop_wrong(heap):
    popped_value = heap[0]
    heap[0] = heap.pop()  # <-- here
    sift_down(heap, 0)
    return popped_value

在那种情况下，如果列表只有一个元素，则根本不应将最后一个元素移到前面。您应该只删除 return 唯一的元素：

def heappop(heap):
    if len(heap) == 1:
        return heap.pop()
    popped_value = heap[0]
    heap[0] = heap.pop()
    sift_down(heap, 0)
    return popped_value

至于 if 的费用，这笔费用微不足道，根本不是您应该担心的事情。

将列表的最后一个元素移动到前面而不用替换旧的前面元素，这在 O(1) 时间内是不可能的。您必须使用不同的数据结构，例如 collections.deque，或者实现您自己的可调整大小 ring buffer。不过，这与堆用例无关。

为了将列表的最后一个元素移到最前面，如果有多个元素则跳过旧的第一个元素，如果只有一个则保持列表不变，if 检查可能是最清楚的，但同样，"leave the list unchanged if there was only one element" 行为实际上对实现 heap-pop 没有用。

Answer 4

一种可行的方法（无一例外，只要 list 不为空）是分配给 list 的一部分：

heap[:1] = (heap.pop(),)

弹出最后一个元素并创建长度为 1 tuple，然后将其分配给 heap，以便它替换第一个元素（如果存在），或者成为 list 如果它是空的（作为 pop 的结果）。它应该保持 O(n) 因为它总是用单个元素替换单个元素；较高的指数未受影响。

如何在 O(1) 时间内将列表中的最后一项移到最前面？

How do I move the last item in a list to the front in O(1) time?

python

heap

python-3.x