用Python实现堆

Question

这基本上是一个简单的堆实现。我只是从C转到Python，我想确保总体上遵循Python的最佳实践。这个堆应该用任何比较函数支持来自任何数据类型的数据。

class Heap(object):
    """"
    Attributes:
        heap: List representation of the heap
        compar(p, c): comparator function, returns true if the relation between p and c is parent-chield
    """
    def __init__(self, compar):
        self.heap = []
        self.compar = compar
    def is_empty(self):
        return len(self.heap) == 0
    def _inv_heapify(self, element_id):
        """
        Do heapifying starting from bottom till it reaches the root.
        """
        while element_id > 0:
            if self.compar(self.heap[element_id / 2], self.heap[element_id]):
                return
            self.heap[element_id / 2], self.heap[element_id] = self.heap[element_id], self.heap[element_id / 2]
            element_id /=2
    def _heapify(self, element_id):
        """
        Do heepifying starting from the root.
        """
        l = len(self.heap)
        if l == 1:
            return
        while 2 * element_id < l:
            el_id = 2 * element_id
            if 2 * element_id + 1 < l and self.compar(self.heap[element_id * 2 + 1], self.heap[element_id * 2]):
                el_id += 1
            if self.compar(self.heap[element_id], self.heap[el_id]):
                return
            self.heap[element_id], self.heap[el_id] = self.heap[el_id], self.heap[element_id]
            element_id = el_id
    def del_min(self):
        if self.is_empty():
            return None
        x = self.heap.pop(0)
        if not self.is_empty():
            self.heap = [self.heap[-1]] + self.heap[0:-1]
            self._heapify (0)
        return x
    def min(self):
        if self.is_empty():
            return None
        return self.heap[0]
    def add(self, element):
        self.heap +=[element]
        self._inv_heapify (len (self.heap) - 1)

Answer 1

谢谢你的伟大问题和伟大的评论@Peilonrayz！没有什么可批评的，只有几件我会亲自改变的事情。这是我的第一个堆实现，所以请仔细检查我的建议.

• 获取父/子文件有点神奇的编号，可能会将其放入一个单独的函数中。
• 在heapify/inv_heapify中，存在着子和父两个词。但是，如果我没有弄错的话，一个真正关注当前节点+其子节点，另一个关注当前节点+其父节点。
• 像"child+=1“这样的台词对我来说有点奇怪。"idx_child+=1“似乎更干净
• 这里正确选择了heapify / inv_heapify这个词吗？维基百科称"heapify:从给定的元素数组中创建一个堆“。因此，我期望一个数组作为函数输入。相反，它接收一个索引..。
• 虽然函数名“比较法”似乎很常见(例如std::string::compare())，但我喜欢用"has“或"is”前缀命名布尔函数返回函数。在max堆的情况下，我们可以将它命名为"is_bigger_than“(类似于operator.gt =”大于“，但可以是自定义函数)

把一切都整合在一起.

class Heap:
    def __init__(self):
        self.lst = []
        self.is_bigger_than = operator.gt

    def add(self, x):
        self.lst.append(x)
        idx_node = len(self.lst) - 1
        self._siftup(idx_node)

    def pop(self):
        if len(self.lst) == 0:
            print("Error: Heap empty!")
        else:
            lst = self.lst
            lst[0], lst[-1] = lst[-1], lst[0]  # switch first with last element
            res = lst.pop()  # pop last element
            self._siftdown(0)
            return res

    def _siftup(self, inode):
        lst = self.lst
        iparent = self._get_parent(inode)
        if iparent >= 0 and self.is_bigger_than(lst[inode], lst[iparent]):
            lst[inode], lst[iparent] = lst[iparent], lst[inode]
            self._siftup(iparent)

    def _siftdown(self, inode):
        lst = self.lst
        ichildren = self._get_children(inode)
        for ichild in ichildren:  # do I need to sift down
            if ichild < len(lst) and self.is_bigger_than(lst[ichild], lst[inode]):
                lst[ichild], lst[inode] = lst[inode], lst[ichild]
                self._siftdown(ichild)

    def _get_parent(self, idx_child):
        idx_parent = int((idx_child - 1) / 2)  # zero-based array
        return idx_parent

    def _get_children(self, idx_parent):
        idx_children = 2 * idx_parent + 1, 2 * idx_parent + 2
        return idx_children