python - Python 中的最小/最大堆实现

Question

这是我在 python 中实现的 MinHeap 和 MaxHeap。这里使用一个比较器来反转MaxHeap中的存储顺序

import heapq


class MinHeap:
    def __init__(self):
        self.heap = []

    def push(self, item):
        heapq.heappush(self.heap, item)

    def pop(self):
        return heapq.heappop(self.heap)

    def peek(self):
        return self.heap[0]

    def __getitem__(self, item):
        return self.heap[item]

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


class MaxHeap(MinHeap):
    def push(self, item):
        heapq.heappush(self.heap, Comparator(item))

    def pop(self):
        return heapq.heappop(self.heap)

    def peek(self):
        return self.heap[0]

    def __getitem__(self, i):
        return self.heap[i].val


class Comparator:
    def __init__(self, val):
        self.val = val

    def __lt__(self, other):
        return self.val > other

    def __eq__(self, other):
        return self.val == other




if __name__ == '__main__':
    max_heap = MaxHeap()
    max_heap.push(12)
    max_heap.push(3)
    max_heap.push(17)
    print(max_heap.pop())

MinHeap 似乎工作正常，但是 MaxHeap 抛出以下错误。

<__main__.Comparator object at 0x10a5c1080>

我似乎不太明白我在这里做错了什么。有人可以帮我解决这个问题吗？

Answer 1

我已将 __repr__ 和 __gt__ 方法添加到您的 Comparator 类中，因此代码现在可以运行，并且 Comparator 实例在打印时显示其 val。

重要的是让这些比较方法在两个 Comparator 实例之间正确进行比较。

您会注意到我已经从 MaxHeap 中删除了大部分方法。它们不是必需的，因为从 MinHeap 继承的方法可以正常工作。您可能希望将其恢复到 MaxHeap

def __getitem__(self, i):
    return self.heap[i].val

取决于您打算如何使用MaxHeap。

import heapq

class MinHeap:
    def __init__(self):
        self.heap = []

    def push(self, item):
        heapq.heappush(self.heap, item)

    def pop(self):
        return heapq.heappop(self.heap)

    def peek(self):
        return self.heap[0]

    def __getitem__(self, item):
        return self.heap[item]

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

class MaxHeap(MinHeap):
    def push(self, item):
        heapq.heappush(self.heap, Comparator(item))

class Comparator:
    def __init__(self, val):
        self.val = val

    def __lt__(self, other):
        return self.val > other.val

    def __eq__(self, other):
        return self.val == other.val

    def __repr__(self):
        return repr(self.val)

if __name__ == '__main__':
    max_heap = MaxHeap()
    max_heap.push(12)
    max_heap.push(3)
    max_heap.push(17)

    while True:
        try:
            print(max_heap.pop())
        except IndexError:
            # The heap's empty, bail out
            break

输出

17
12
3

为Comparator提供全套丰富的比较方法可能是一个好主意。上面的代码工作不需要它们，但它们将使 Comparator 实例更加灵活。因此，如果您需要它们，它们在这里:

def __lt__(self, other):
    return self.val > other.val

def __le__(self, other):
    return self.val >= other.val

def __gt__(self, other):
    return self.val < other.val

def __ge__(self, other):
    return self.val <= other.val

def __eq__(self, other):
    return self.val == other.val

def __ne__(self, other):
    return self.val != other.val