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)

现在，当我将项目添加到队列时，它们运行良好。说，我把它放到终端：

pq = PriorityQueue()
pq.add(1)
pq.add(2)
pq.add(45)
pq.add(4)
pq.add(41)
pq.add(5)

pq.__str__()

我得到的是“[1,2,5,4,41,45]”。所以它看起来只是在某种程度上 sift_up() ，它并没有完全重新排序堆。

编辑：每当我向队列中添加“1”时，它似乎都搞砸了。在这个例子中，每次添加后我都有它 return:

>>> 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]

所以这个结果符合您编码的方式 sift_up。

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

In [18]: import heapq

In [19]: x = [5, 53, 531, 5131, 1]

In [20]: heapq.heapify(x)

In [21]: x
Out[21]: [1, 5, 531, 5131, 53]

Python 堆优先队列 sift_up()

Python Heap Priority Queue sift_up()

python

queue

heap

priority-queue