把一个无序的binarytree二叉树堆调整成一个标准大顶堆，非递归，python
import random
from binarytree import build
def app():
data = []
SIZE = 10
for i in range(SIZE):
data.append(i)
# 随机打乱数据
random.shuffle(data)
my_tree = build(data)
print('原二叉树堆:', my_tree)
print('是大顶堆吗?', my_tree.is_max_heap)
nodes = my_tree.levelorder
print(nodes)
print('-----')
while True:
ok = check(my_tree)
if ok:
print('调整二叉树堆完成')
break
adjust(my_tree)
print(my_tree)
print(my_tree.levelorder)
print('是大顶堆吗?', my_tree.is_max_heap)
"""
如果已经是标准的大顶堆，那么数组中存储的数据，必然符合以下规律:
array[i]>array[2*i+1] 并且 array[i]>array[2*i+2] ， 即根节点大于任何子节点
如果不符合上述判断条件，那么该数组还不是大顶堆，需要继续调整。
注意，i的区间是0到array.size/2 - 1
在循环检测时候，小心数组越界情况。
"""
def check(my_tree):
val = my_tree.values
flag = True
for i in range(int(my_tree.size / 2)):
i1 = 2 * i + 1
i2 = 2 * i + 2
if i1 < my_tree.size:
if val[i] > val[i1]:
flag = True
else:
flag = False
break
if i2 < my_tree.size:
if val[i] > val[i2]:
flag = True
else:
flag = False
break
return flag
# 对无序的二叉树堆进行调整，把二叉树堆调整成一个大顶堆。
def adjust(my_tree):
idx = int(my_tree.size / 2) - 1
nodes = my_tree.levelorder
while idx >= 0:
i1 = 2 * idx + 1
i2 = 2 * idx + 2
if i1 < my_tree.size:
if nodes[i1].value > nodes[idx].value:
swap(nodes[idx], nodes[i1])
if i2 < my_tree.size:
if nodes[i2].value > nodes[idx].value:
swap(nodes[idx], nodes[i2])
idx = idx - 1
# 交换节点的值
def swap(a, b):
t = a.value
a.value = b.value
b.value = t
if __name__ == '__main__':
app()
输出：
原二叉树堆:
____7__
/
__6__ 5
/ /
3 0 2 1
/ /
9 4 8
是大顶堆吗? False
[Node(7), Node(6), Node(5), Node(3), Node(0), Node(2), Node(1), Node(9), Node(4), Node(8)]
-----
调整二叉树堆完成
____9__
/
__8__ 5
/ /
6 7 2 1
/ /
3 4 0
[Node(9), Node(8), Node(5), Node(6), Node(7), Node(2), Node(1), Node(3), Node(4), Node(0)]
是大顶堆吗? True
