Python 筛选法实现最大堆的构建、插入、删除算法

最大树（最小树）：每个结点的值都大于（小于）或等于其子节点（如果有的话）的值的树。

最大堆（最小堆）：最大（最小）的完全二叉树

向下调整法：对于某个结点i，将其与左右子结点中值较大的一个进行比较，如果i的值小于该子节点的值，则将两个结点交换位置；重复上述步骤，直到结点m不再小于左右子结点中值较大的那个或者结点m为叶子结点为止。

向上调整法：对于某个结点i，将其与父节点进行比较，如果i的值大于父节点的值，则交换两个结点的位置，重复上述步骤，直到新结点的值不再大于父节点的值或者新结点成为根节点为止。

最大堆的构建——筛选法：首先将待排序的所有关键码放入到一颗完全二叉树的各个结点中，显然，叶子结点无需做调整；从第一个具有孩子的结点i开始(,符号代表小于等于x的最大整数)，如果以这个元素为根的子树已是最大堆，则无需调整，否则采用向下调整法调整子树使之成为堆。继续检查i-1，i-2等结点为根的子树，直到该二叉树的根结点（位置为0）被检查并调整结束。

最大堆的插入：将新结点插入到该树的最末尾位置上，对该结点采用向上调整法，使其满足最大堆。

最大堆的删除：将完全二叉树最末尾结点m和待删除结点p交换位置，删除结点p，先用结点m与其父节点进行比较，如果该结点的值大于父节点的值，则采用向上调整法；否则，用结点m与其左右子结点中值较大的一个进行比较，如果该结点的值小于该子节点的值，则采用向下调整法。

例如数组 array = [20,12,35,15,10,80,30,17,2,1]，构建最大堆如下：

代码如下

heaparray = [20,12,35,15,10,80,30,17,2,1]
'''
筛选法构造最大堆
'''
def BuildMeap():
    i = int( len(heaparray)/2 - 1)
    while(i>=0):
        SiftDown(i)
        i-=1
'''
向下调整
'''        
def SiftDown(parent):
    i = parent
    j = 2*i+1
    tmp = heaparray[parent]
    while(j<len(heaparray)):
        if((j<len(heaparray)-1) and heaparray[j]<heaparray[j+1]):
            j+=1
        if(tmp < heaparray[j]):
            heaparray[i] = heaparray[j]
            i = j
            j = 2*i + 1
        else: break
    heaparray[i] = tmp

def getParentPos(position):
    if((position-1)/2>=0): return int((position-1)/2 )
    else: return 0
'''
向上调整
''' 
def SiftUp(position):
    tmpposition = position
    tmp = heaparray[tmpposition]
    while((tmpposition>0) and (heaparray[getParentPos(tmpposition)]<tmp)):
        heaparray[tmpposition] = heaparray[getParentPos(tmpposition)]
        tmpposition = getParentPos(tmpposition)
    heaparray[tmpposition] = tmp
'''
插入结点
''' 
def Insert(node):
    heaparray.append(node)
    SiftUp(len(heaparray)-1)
'''
移除最大值
''' 
def RemoveMax():
    if(len(heaparray) == 0):
        return None
    else:
        tmp = heaparray[0]
        heaparray[0] = heaparray[len(heaparray)-1]
        heaparray.pop()
        if(len(heaparray)>1):SiftDown(0)
        return tmp
'''
删除任意结点
'''   
def DeleteNode(position):
    if(position<0 or (position>=len(heaparray))): return False
    heaparray[position] = heaparray[len(heaparray)-1]
    heaparray.pop()
    if((position>0) and heaparray[position] > heaparray[getParentPos(position)]):
        SiftUp(position)
    else:
        SiftDown(position)
    return True

测试代码

if __name__=='__main__':
    for i in range(len(heaparray)):
        print(heaparray[i],end = ' ')
    print()
    BuildMeap()
    Insert(40)
    for i in range(len(heaparray)):
        print(heaparray[i],end = ' ')
    print()
    bool = DeleteNode(8)
    print(bool)
    val = RemoveMax()
    print(val)
    for i in range(len(heaparray)):
        print(heaparray[i],end = ' ')

输出结果

20 12 35 15 10 80 30 17 2 1 
80 40 35 15 17 20 30 12 2 1 10 
True
80
40 17 35 15 1 20 30 12 10