2

这是我在 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>

我似乎不太明白我在这里做错了什么。有人可以帮我弄这个吗。

4

1 回答 1

3

我已经为您的类添加了__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
于 2018-05-07T19:14:44.107 回答