Python堆实现

Question

我制作了这个片段来复习我的DS教科书。用函数_upheap和_downheap编写迭代循环可以吗？欢迎任何其他建议或反馈。谢谢。

# heap.py
# by kidkkr
# Mar-14-2017, 07:29PM

class Heap:
    __slots__ = '_data'

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

    def __len__(self):
        return len(self._data)

    def isEmpty(self):
        return len(self) == 0

    def add(self, item):
        self._data.append(item)
        self._upheap(len(self) - 1)

    def del_min(self):
        self._swap(0, len(self) - 1)
        res = self._data.pop()
        self._downheap(0)
        return res

    def _left(self, j):
        return 2*j + 1

    def _hasLeft(self, j):
        return self._left(j) < len(self)

    def _right(self, j):
        return 2*j + 2

    def _hasRight(self, j):
        return self._right(j) < len(self)

    def _parent(self, j):
        return (j - 1)/2

    def _swap(self, i, j):
        self._data[i], self._data[j] = \
            self._data[j], self._data[i]

    def _upheap(self, j):
        while j > 0 and self._data[j] < self._data[self._parent(j)]:
            self._swap(j, self._parent(j))
            j = self._parent(j)

    def _downheap(self, j):
        while j < len(self):
            if self._hasLeft(j):
                smallChild = self._left(j)
                if self._hasRight(j) and \
                    self._data[smallChild] > self._data[self._right(j)]:
                    smallChild = self._right(j)
                if self._data[j] > self._data[smallChild]:
                    self._swap(j, smallChild)
                    j = smallChild
                else:
                    break
            else:
                break


if __name__ == "__main__":
### Test Codes
    a = Heap()
    a.add(21)
    a.add(28)
    a.add(16)
    a.add(9)
    a.add(14)
    a.add(21)
    a.add(26)
    a.add(33)
    a.add(22)
    a.add(6)
    a.add(22)
    print(a.del_min())
    print(a.del_min())
    print(a.del_min())
    print(a.del_min())
    print(a.del_min())
    print(a.del_min())
    print(a.del_min())
    print(a.del_min())
    print(a.del_min())
    print(a.del_min())
    print(a.del_min())

Answer 1

您的方法isEmpty根本不需要。首先，您的代码中没有一个使用它。其次，如果要保留它，就应该将它的逻辑转换为__bool__，这样，如果堆不是空的，if heap就会自动工作，并且是True。但是第三，如果不存在__bool__方法，Python已经调用len(obj) != 0来确定对象的真实性，因此它已经通过定义__len__提供了。

作为第二点，您不应该混淆命名约定。当前，lower_case和camelCase都用于​方法名。PEP8，Python的官方风格指南，推荐使用lower_case。

您不需要在这里继续行，行已经小于80个字符：

    def _swap(self, i, j):
        self._data[i], self._data[j] = self._data[j], self._data[i]

一些docstrings描述了您的方法所做的事情，以及它们期望作为输入/返回的内容，这也是非常好的。

我会将您的方法del_min重命名为pop_min，因为它返回已删除的元素，而不仅仅是删除它。