把一个无序的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