完全二叉树小顶堆插入和删除节点，非递归，binarytree，Python

超、凢脫俗 2023-10-02 16:03 1阅读 0赞

import binarytree
    from binarytree import heap, get_parent
    
    
    def app():
        # 构建一个小顶堆
        hp = heap(height=3, is_max=False, is_perfect=False)
        print(hp)
    
        print('-')
        # 在堆中插入一个节点
        values = hp.values
        values.append(99999)
        hp = binarytree.build(values)
    
        while not ok(hp):
            adjust(hp)
    
        print(hp)
        print('是小顶堆吗?', hp.is_min_heap)
    
        print('--')
        # 在堆中删除顶点（最小值）
        values = hp.values
        del (values[0])
        hp = binarytree.build(values)
    
        while not ok(hp):
            adjust(hp)
    
        print(hp)
        print('是小顶堆吗?', hp.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()

输出：

_____0__
           /        \
        __1___       2
       /      \     / \
      4       _8   6   12
     / \     /
    7   9   13
    
    -
    
            ___________0__
           /              \
        __1___             2
       /      \           / \
      4       _8__       6   12
     / \     /    \
    7   9   13   99999
    
    是小顶堆吗? True
    --
    
             ________1___
            /            \
        ___2______       _4
       /          \     /  \
      8          __6   12   7
     / \        /
    9   13   99999
    
    是小顶堆吗? True