0

我写了一个min-max heap，即找到最小值和最大值的堆是常量操作。现在我想为我的类创建测试，所以我决定实现一个函数来检查堆是否是最小最大堆。在这里，但我不确定它是否 100% 正确。

def is_min_max_heap(h):
    if not isinstance(h, MinMaxHeap):
        return False
    if h.heap:
        for item in h.heap:
            if not isinstance(item, HeapNode):
                return False
        for i, item in reversed(list(enumerate(h.heap))):
            g = h.grandparent_index(i)
            if g is not None:
                if h.is_on_even_level(i):
                    if h.heap[g] > item:
                        return False
                else:
                    if h.heap[g] < item:
                        return False            
    return True

请注意，这个堆的元素用 class 表示HeapNode，这就是我检查是否self.heap只包含该类的对象的原因。偶数级别例如为 0、2、4 等。此堆的最小值位于self.heap[0]. 最大值是max(self.heap[1], self.heap[2])（前提是两者都存在）。如果节点 at 的祖父母不存在，则h.grandparent_index(i)返回。Nonei

我的算法的想法很简单。我从底部开始，检查我是否处于奇数水平。如果在一个均匀的水平上，那么我必须确保该元素大于其祖父母。如果我处于奇怪的水平，我必须确保它比它的祖父母小。

我的算法正确吗？我错过了一些观点吗？如果它是正确的，改进它的建议会被广泛接受。

最终我的实现可能对其他人有用。

编辑 1

我刚刚注意到我的函数检查偶数（和奇数）级别中的元素是否正确布置，但它不检查最大元素是否位于self.heap[1]或self.heap[2]并且最小元素是否位于self.heap[0]。

编辑 2

我正在根据编辑 1 和@goCards 的答案添加新的更新代码。

def is_min_max_heap(h) -> bool:
    """Returns `True` if `h` is a valid `MinMaxHeap` object. `False` otherwise."""
    if not isinstance(h, MinMaxHeap):
        return False

    if h.heap:
        for item in h.heap:
            if not isinstance(item, HeapNode):
                return False

        if h.size() == 1:
            return True

        if h.size() == 2:
            return max(h.heap) == h.heap[1] and min(h.heap) == h.heap[0]

        if h.size() >= 3:
            if (h.heap[0] != min(h.heap) or
                (h.heap[1] != max(h.heap) and
                 h.heap[2] != max(h.heap))):
                return False

        for i, item in reversed(list(enumerate(h.heap))):
            p = h.parent_index(i)

            if p != -1:
                if h.is_on_even_level(i):
                    if h.heap[p] < item:
                        return False
                else:
                    if h.heap[p] > item:
                        return False

            g = h.grandparent_index(i)
            if g != -1:
                if h.is_on_even_level(i):
                    if h.heap[g] > item:
                        return False
                else:
                    if h.heap[g] < item:
                        return False
    return True
4

2 回答 2

1

一种更简单的方法是从堆中删除元素。该算法将是这样的：

  • 弹出 min-max 并将它们存储在一个数组中
  • 重复直到堆中不再有元素
  • 检查数组是否具有您期望的特征。

在弹出堆中的所有元素后检查您生成的数组，您应该有严格增加的偶数索引和严格减少的奇数索引。如果这不是真的，那么您的堆实现是错误的。

于 2016-02-19T00:37:39.457 回答
0

您的算法缺少一些检查。考虑下面的示例，它不是最小-最大堆，但通过了您的测试。将 5 视为根。根有另一个分支，但为简单起见未显示。

使用您的算法，下面的堆被声明为最小-最大堆，但它不满足最小-最大堆属性。您的算法还需要检查父节点。

编辑：最小最大堆是满足两个属性的二叉树：

1) T 具有堆形

2) T 是最小-最大排序的：存储在偶数（奇数）级别的节点的值小于或等于存储在其根位于零级别的后代（如果有）的值。

例子

for i, item in reversed(list(enumerate(h.heap))):
    g = h.grandparent_index(i)
    p = h.parent_index(i)
    if g is not None and p is not None:
        if h.is_on_even_level(i):
            if item > h.heap[g]: pass #grandparent should be smallest in its subtree
            else: return False
            if item < h.heap[p]: pass #parent should be greatest in its subtree
            else: return False
        else: #odd level
            if item < h.heap[g]: pass #grandparent should be greatest in its subtree
            else: return False
            if item > h.heap[p]: pass #parent should be smallest in its subtree
            else: return False
于 2016-02-19T00:29:15.277 回答