如何在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)访问给定indeces的元素(因此它不能是链表).

Answer 1

听起来你正在实现一个堆,这一行是heap-pop操作实现的一部分.在上下文中,它看起来像

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

在这种情况下,如果列表只有一个元素,则不应将最后一个元素移到前面.你应该删除并返回唯一的元素:

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,或实现您自己的可调整大小的环缓冲区.但这与堆用例无关.

为了将列表的最后一个元素移动到前面,如果有多个元素则重复旧的第一个元素,如果只有一个元素则保持列表不变,则if检查可能是最清晰的,但同样,"保持列表保持不变如果只有一个元素"行为实际上对实现堆弹出没有用.