把一个无序的binarytree二叉树堆调整成一个标准大顶堆，非递归，python

忘是亡心i 2023-10-02 15:27 1阅读 0赞

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