2

我在网上搜索了这个在 Python 中实现 MinHeap 和 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.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) 时间内的东西。

4

1 回答 1

3

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

self.heap[0]

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

于 2018-02-18T20:22:05.357 回答