Min/Max 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 class，因此代码现在运行，并且 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

Min/Max Python 中的堆实现

Min/Max Heap implementation in Python

python

min-heap

python-3.x

max-heap