有没有Python方法来检查二叉树是否是最小堆？

Question

如何编写一个可以接受二叉树作为参数的函数，如果它是最小堆则返回 True，否则返回 False。

from heapq import heapify

def binary_heap(tree):
  while len(tree) > 1:
    if heapify(tree):
        return True
    else:
        return False

Answer 1

您可以迭代所有子节点以验证它们是否大于其父节点：

def is_minheap(lst):
    return all(lst[i - 1 >> 1] <= lst[i] for i in range(len(lst) - 1, 0, -1))

这样：

from heapq import heapify
from random import sample

lst = sample(range(10), 10)
print(is_minheap(lst), lst)
heapify(lst)
print(is_minheap(lst), lst)

输出类似：

False [2, 8, 9, 0, 6, 5, 3, 1, 4, 7]
True [0, 1, 3, 2, 6, 5, 9, 8, 4, 7]