如何编写可以接受二叉树作为参数的函数,如果它是最小堆,则返回True,如果不是,则返回False.
from heapq import heapify
def binary_heap(tree):
while len(tree) > 1:
if heapify(tree):
return True
else:
return False
如何编写可以接受二叉树作为参数的函数,如果它是最小堆,则返回True,如果不是,则返回False.
from heapq import heapify
def binary_heap(tree):
while len(tree) > 1:
if heapify(tree):
return True
else:
return False
由于最小堆必须满足每heapq
‘S documentation:
heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2]
您可以遍历所有子 node 以验证它们是否大于或等于其父 node (请注意,i - 1 >> 1
是(i - 1) // 2
When i > 0
的缩写):
def is_minheap(lst):
return all(lst[i] >= lst[i - 1 >> 1] for i in range(1, len(lst)))
因此:
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 [1, 2, 6, 8, 0, 5, 3, 9, 7, 4]
True [0, 1, 3, 7, 2, 5, 6, 9, 8, 4]