创建一个给出错误结果的二进制堆实现

creating a binary heap implementation giving wrong result

我正在按照在线课程实现二进制堆,并且我完成了以下操作:

from __future__ import division

class BinaryHeap(object):
    def __init__(self, arr=None):
        self.heap = []

    def insert(self, item):
        self.heap.append(item)
        self.__swim(len(self.heap) - 1)

    def __swim(self, index):
        parent_index = (index - 1) // 2
        while index > 0 and self.heap[parent_index] < self.heap[index]:
            self.heap[parent_index], self.heap[index] = self.heap[index], self.heap[parent_index]
            index = parent_index

现在,我将其用作:

s = 'SORTEXAMPLE'
a = BinaryHeap()

for c in s:
    a.insert(c)

现在,在这之后堆被排序为:

['S', 'T', 'X', 'P', 'L', 'R', 'A', 'M', 'O', 'E', 'E']

而不是

['X', 'T', 'S', 'P', 'L', 'R', 'A', 'M', 'O', 'E', 'E']

所以,似乎最后一次交流没有发生,我想我可能搞砸了索引,但我找不到任何明显的问题。

好的,我明白了。当然,我不能在循环外缓存 parent_index

代码应该是:

def __swim(self, index):
    while index > 0 and self.heap[(index - 1) // 2] < self.heap[index]:
        self.heap[(index - 1) // 2], self.heap[index] = self.heap[index], self.heap[(index - 1) // 2]
        index = (index - 1) // 2

我很惊讶这之前没有进入无限循环....