sortlist=[4,72,81,6,73,124,65,68,66]

class Node(object):
    def __init__(self,value):
        self.left=None
        self.right=None
        self.value=value
        self.p=None

def buidtree(tree):   #   返回树的非空节点个数
    if tree==None:
        return 0
    elif tree.left==None and tree.right==None:
        return 1
    return buidtree(tree.left)+buidtree(tree.right)+1
    
def createTree(tree,value):    #  创建树
    if tree.left==None:
        tree.left=Node(value)
        tree.left.p=tree
        return
    elif tree.right==None:
        tree.right=Node(value)
        tree.right.p=tree
        return
    if buidtree(tree.left)-buidtree(tree.right)*2==1:   #   判断加入左还是右
        createTree(tree.right,value)
    else:
        createTree(tree.left,value)

root=Node(sortlist[0])
for i in sortlist[1:]:
    createTree(root,i)

def firstbult(tree):    #   先序遍历
    if tree==None:
        return []
    else:
        return [tree.value]+firstbult(tree.left)+firstbult(tree.right)

def mbult(tree):    #   中序遍历
    if tree==None:
        return []
    else:
        return mbult(tree.left)+[tree.value]+mbult(tree.right)

def min(a,b):
    if a<=b:
        return a
    else :
        return b
def initdui(node,ccount):   #   初始化堆   小根堆
    if node==None or node.left==None:
        return ccount
    elif node.right==None:
        if node.value>node.left.value:
            ccount+=1
            tmpe=node.value 
            node.value=node.left.value   #   局部排序    
            node.left.value=tmpe
        return ccount
    else :
        if node.value>node.left.value:
            ccount+=1
            tmpe=node.value 
            node.value=node.left.value   #   局部排序    
            node.left.value=tmpe
        if node.right.value<node.value:
            ccount+=1
            tmpe=node.value 
            node.value=node.right.value   #   局部排序    
            node.right.value=tmpe
        cc=initdui(node.left,ccount)
        return initdui(node.right,cc)
    
def usedui(node):                              #  返回堆最后的元素
    if node.left==None and node.right==None:
        value=node.value
        if node.p!=None and node.p.left==node:             #   删除这个节点
            node.p.left=None
        elif node.p!=None:
            node.p.right=None
        return value
    elif buidtree(node.left)>buidtree(node.right):
        return usedui(node.left)
    else:                          #   相等时走右边
        return usedui(node.right)
def newdui(node,value):
    node.value=value
    if node.left!=None:
        if node.value>node.left.value and node.right==None:
            node.value=node.left.value
            newdui(node.left,value)
        elif node.right!=None :
            minvalue=min(node.left.value,node.right.value)
            if minvalue==node.left.value and minvalue<node.value:
                node.value=node.left.value
                newdui(node.left,value)
            elif minvalue<node.value:
                node.value=node.right.value
                newdui(node.right,value)
            

root=Node(sortlist[0]) 
for i in sortlist[1:]: # 构造完全二叉树
    createTree(root,i)
cishu=-1
count=0
while cishu!=count:
    cishu=count
    count=initdui(root,cishu)           #初始化堆
print('初始化堆用的次数',count)
print('先序堆',firstbult(root))
print('原始列',sortlist)

duipaixu=[]
while root.left!=None:
    duipaixu.append(root.value)
    value=usedui(root)
    newdui(root,value)
duipaixu.append(root.value)    
print('排序后',duipaixu)

输出的结果

初始化堆用的次数 3
先序堆 [4, 6, 65, 72, 68, 73, 66, 124, 81]
原始列 [4, 72, 81, 6, 73, 124, 65, 68, 66]

10-04 15:14