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

水深无声 2022-05-18 02:34 126阅读 0赞

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

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

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

**向上调整法**：对于某个结点i，将其与父节点![parent=\\left \\lfloor \\left ( i-1 \\right )/2 \\right \\rfloor][parent_left _lfloor _left _ i-1 _right _2 _right _rfloor]进行比较，如果i的值大于父节点的值，则交换两个结点的位置，重复上述步骤，直到新结点的值不再大于父节点的值或者新结点成为根节点为止。

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

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

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

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

![70][]

代码如下

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

[parent_left _lfloor _left _ i-1 _right _2 _right _rfloor]: https://private.codecogs.com/gif.latex?parent%3D%5Cleft%20%5Clfloor%20%5Cleft%20%28%20i-1%20%5Cright%20%29/2%20%5Cright%20%5Crfloor
[i_left _lfloor n_2 _right _rfloor-1]: https://private.codecogs.com/gif.latex?i%3D%5Cleft%20%5Clfloor%20n/2%20%5Cright%20%5Crfloor-1
[left _lfloor x _right _rfloor]: https://private.codecogs.com/gif.latex?%5Cleft%20%5Clfloor%20x%20%5Cright%20%5Crfloor
[70]: /images/20220518/5db040c7b63e4d239be481358c3912cb.png