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

Question

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

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

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

Answer 1

好的，我明白了。当然，我不能在循环外缓存 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

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

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

creating a binary heap implementation giving wrong result

python

heapsort

binary-heap