python - Python 中的 MinHeap/MaxHeap 实现

Question

我在网上搜索了 MinHeap 和 Maxheap 的 Python 实现。

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.h)

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

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


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

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

    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 > self.other

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

    def __str__(self):
        return str(self.val)

现在我需要为这两个类添加一个 peek 方法。在当前的实现中，我可以弹出并向后推。但我的问题是，有没有更好的方法来做到这一点。 O(1) 时间内的东西。

Answer 1

这些类基于 Python 的 heapq 结构，该结构建立在标准的 Python 列表之上。最小堆中的最小项和最大堆中的最大项位于索引零处。所以就返回

self.heap[0]

如果堆为空，则会导致错误，但这可能正是您想要的。