无序binarytree二叉树堆调整成小顶堆，基于节点图，非数组内操作，非递归，python

古城微笑少年丶 2023-10-02 15:38 12阅读 0赞

直接使用图中的节点父子关系循环遍历，不像之前那样在数组内操作排序。

import random
    
    from binarytree import build, get_parent
    
    
    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_min_heap)
    
        print('-----')
    
        while not ok(my_tree):
            adjust(my_tree)
    
        print(my_tree)
        print('是小顶堆吗?', my_tree.is_min_heap)
    
    
    def adjust(my_tree):
        nodes = my_tree.levelorder
    
        while len(nodes) != 0:
            node = nodes.pop()
    
            p = get_parent(my_tree, node)
            left = node.left
            right = node.right
    
            if left is not None:
                if left.value < node.value:
                    swap(left, node)
    
            if right is not None:
                if right.value < node.value:
                    swap(right, node)
    
            if p is not None:
                if node.value < p.value:
                    swap(node, p)
    
    
    def ok(my_tree):
        nodes = my_tree.levelorder
    
        done = True
        while len(nodes) != 0:
            p = nodes.pop()
    
            left = p.left
            right = p.right
    
            if left is not None:
                if p.value > left.value:
                    done = False
                    break
    
            if right is not None:
                if p.value > right.value:
                    done = False
                    break
    
        return done
    
    
    # 交换节点的值
    def swap(a, b):
        t = a.value
        a.value = b.value
        b.value = t
    
    
    if __name__ == '__main__':
        app()

输出：

____4__
           /       \
        __0__       1
       /     \     / \
      8       6   5   9
     / \     /
    7   2   3
    
    是小顶堆吗? False
    -----
    
            ____0__
           /       \
        __1__       4
       /     \     / \
      2       3   5   9
     / \     /
    7   8   6
    
    是小顶堆吗? True