Python堆优先队列sift_up()

Question

我对Python还是比较陌生的，但是在堆优先级队列方面有一个问题。下面是我的init（），str（）、add（）和我的sift_up（）方法：

def __init__(self):
    self.queue = []

def __str__(self):
    return str(self.queue)

def add(self, item):
    self.queue.append(item)
    self.sift_up(len(self.queue) - 1)

def sift_up(self, item):
    parent = (item - 1) // 2
    if parent >= 0 and self.queue[parent] > self.queue[item]:
        self.queue[parent], self.queue[item] = self.queue[item], self.queue[parent]
        self.sift_up(parent)

现在，当我向队列中添加项目时，它们可以正常运行。我把这个放进了终端：

^{pr2}$

我得到的是“[1,2,5,4,41,45]”。所以它看起来只是稍微筛选一下，并没有完全重新排序堆。在

编辑：每当我向队列中添加“1”时，它似乎就搞砸了。在这个例子中，我让它在每次添加后返回：

>>> pq.add(5)
[5]
>>> pq.add(53)
[5, 53]
>>> pq.add(531)
[5, 53, 531]
>>> pq.add(5131)
[5, 53, 531, 5131]
>>> pq.add(1)
[1, 5, 531, 5131, 53]
>>>

所以它取[1]处的任何元素并将其放在队列的后面。我确信这是微不足道的，但是作为Python的新手，我似乎不知道为什么。 再次感谢您的帮助！谢谢。在

Answer 1

在示例数据[5, 53, 531, 5131]中，您在sift_up中表示的计算将如下所示：

# Append 1 to the end
 > [5, 53, 531, 5131, 1]

# The index for '1' is 4, so 'item' is 4.
# (4-1) // 2 = 1 (and 1 >= 0), so 'parent' is 1.
# The value at 'parent' is 53. 53 > 1 is true.
# So swap the value 53 with the value at the end of the list.
 > [5, 1, 531, 5131, 53]

# Now repeat, 'item' starts out at 1.
# The index at (1 - 1) // 2 = 0 (And 0 >=0) so 'parent' is 0.
# The value at index 0 is 5. 5 > 1 is true.
# So swap the value 5 with the value at 'item' (1) to get
 > [1, 5, 531, 5131, 53]

{cd2>从逻辑上遵循cd2}的结果。在

标准库的heapq.heapify函数也会产生相同的结果：看起来这是优先级队列的正确行为：

^{pr2}$