题解 | #【模板】堆:一组数据实现最大堆 or 空数据逐步实现最大堆的步骤#

【模板】堆

http://www.nowcoder.com/practice/13f61c8c92404f5ea5d6fa4c692869fb

最大堆的实现

目标:实现最大堆的构建以及调整->主要为添加一个元素或者弹出一个元素后的调整

ACM模式中类的声明及初始化:

class MyHeap(object):
    def __init__(self):
        # 定义一个大根堆
        self.heap = []
        # 默认大根堆的大小
        self.length = 0

if __name__ == '__main__':

    A = MyHeap()

类中的方法实现:主要为对堆调整

class MyHeap(object):
    def __init__(self):
        # 定义一个大根堆
        self.heap = []
        self.length = 0
        
    # 对堆的调整:堆是一个完全二叉树,通过找到第一个非叶子节点的位置,并调整该节点与左右孩子的大小关系,使其实现最大堆的性值:根节点的值大于左右孩子的值
    def heapAdjust(self, root, size):
    
        # NoLeaf ->非叶子节点
        largest = root
        
        # 左孩子位置
        left = root * 2 + 1
        
        # 右孩子位置
        right = root * 2 + 2
        
        # 寻找出 这三个位置的最大值所在位置
        if left < size and self.heap[left] > self.heap[largest]:
            largest = left
        if right < size and self.heap[right] > self.heap[largest]:
            largest = right
            
        # 判断是否满足最大堆性质
        if largest != root:
            self.heap[largest],self.heap[root] = self.heap[root],self.heap[largest]
            
            # 根节点调整完后,继续查看 以子节点为根节点的子树是否满足最大堆性质
            self.heapAdjust(largest,self.length)

堆的插入:将插入元素放在最大堆对应的数组末尾,插入元素之前,数组中的结构为一个最大堆,只需要为新插入的元素寻找到合适的位置

class MyHeap(object):
    def __init__(self):
        # 定义一个大根堆
        self.heap = []
        self.length = 0
        
    # 对堆的调整:堆是一个完全二叉树,通过找到第一个非叶子节点的位置,并调整该节点与左右孩子的大小关系,使其实现最大堆的性值:根节点的值大于左右孩子的值
    def heapAdjust(self, root, size):
    
        # NoLeaf ->非叶子节点
        largest = root
        
        # 左孩子位置
        left = root * 2 + 1
        
        # 右孩子位置
        right = root * 2 + 2
        
        # 寻找出 这三个位置的最大值所在位置
        if left < size and self.heap[left] > self.heap[largest]:
            largest = left
        if right < size and self.heap[right] > self.heap[largest]:
            largest = right
            
        # 判断是否满足最大堆性质
        if largest != root:
            self.heap[largest],self.heap[root] = self.heap[root],self.heap[largest]
            
            # 根节点调整完后,继续查看 以子节点为根节点的子树是否满足最大堆性质
            self.heapAdjust(largest,self.length)

    def heap_push(self, val):
        self.heap.append(val)
        self.length += 1
        
        # 插入节点的父节点到根节点已经是有序的 只需要为新插入节点找到一个合适的位置
        newRoot = self.length - 1
        
        # 如果当前节点被换到堆顶,则调整结束:如果当前节点数据大于父节点数据,那么就进行交换
        while newRoot and (self.heap[newRoot] > self.heap[(newRoot - 1) // 2]):
            self.heap[newRoot],self.heap[(newRoot-1)//2] = self.heap[(newRoot - 1) //2],self.heap[newRoot]
            newRoot = (newRoot-1)//2

堆的弹出:弹出数组的头元素,即最大堆的最大值,然后维护整个数组。首先,保存弹出的值,将数组的头与尾交换,将尾部弹出。然后,维护长度减一后的数组,使其满足最大堆性质,heapAdjust 传入参数的'root'为堆顶位置'0' :-> '数组索引'

class MyHeap(object):
    def __init__(self):
        # 定义一个大根堆
        self.heap = []
        self.length = 0
        
    # 对堆的调整:堆是一个完全二叉树,通过找到第一个非叶子节点的位置,并调整该节点与左右孩子的大小关系,使其实现最大堆的性值:根节点的值大于左右孩子的值
    def heapAdjust(self, root, size):
    
        # NoLeaf ->非叶子节点
        largest = root
        
        # 左孩子位置
        left = root * 2 + 1
        
        # 右孩子位置
        right = root * 2 + 2
        
        # 寻找出 这三个位置的最大值所在位置
        if left < size and self.heap[left] > self.heap[largest]:
            largest = left
        if right < size and self.heap[right] > self.heap[largest]:
            largest = right
            
        # 判断是否满足最大堆性质
        if largest != root:
            self.heap[largest],self.heap[root] = self.heap[root],self.heap[largest]
            
            # 根节点调整完后,继续查看 以子节点为根节点的子树是否满足最大堆性质
            self.heapAdjust(largest,self.length)

    def heap_push(self, val):
        self.heap.append(val)
        self.length += 1
        
        # 插入节点的父节点到根节点已经是有序的 只需要为新插入节点找到一个合适的位置
        newRoot = self.length - 1
        
        # 如果当前节点被换到堆顶,则调整结束:如果当前节点数据大于父节点数据,那么就进行交换
        while newRoot and (self.heap[newRoot] > self.heap[(newRoot - 1) // 2]):
            self.heap[newRoot],self.heap[(newRoot-1)//2] = self.heap[(newRoot - 1) //2],self.heap[newRoot]
            newRoot = (newRoot-1)//2
            
    def heap_pop(self):
        # 输出堆顶元素:也就是self.heap[0]
        if len(self.heap) == 0:
            print('empty')
        else:
            ans = self.heap[0]
            # 将堆顶元素调换到最后  对堆顶进行调整
            self.heap[0],self.heap[-1] = self.heap[-1],self.heap[0]
            # 弹出元素
            self.heap.pop()
            # 大小减一
            self.length -= 1
            self.heapAdjust(0, self.length)
            print(ans)    

获取最大堆的堆顶元素

class MyHeap(object):
    def __init__(self):
        # 定义一个大根堆
        self.heap = []
        self.length = 0
        
    # 对堆的调整:堆是一个完全二叉树,通过找到第一个非叶子节点的位置,并调整该节点与左右孩子的大小关系,使其实现最大堆的性值:根节点的值大于左右孩子的值
    def heapAdjust(self, root, size):
    
        # NoLeaf ->非叶子节点
        largest = root
        
        # 左孩子位置
        left = root * 2 + 1
        
        # 右孩子位置
        right = root * 2 + 2
        
        # 寻找出 这三个位置的最大值所在位置
        if left < size and self.heap[left] > self.heap[largest]:
            largest = left
        if right < size and self.heap[right] > self.heap[largest]:
            largest = right
            
        # 判断是否满足最大堆性质
        if largest != root:
            self.heap[largest],self.heap[root] = self.heap[root],self.heap[largest]
            
            # 根节点调整完后,继续查看 以子节点为根节点的子树是否满足最大堆性质
            self.heapAdjust(largest,self.length)

    def heap_push(self, val):
        self.heap.append(val)
        self.length += 1
        
        # 插入节点的父节点到根节点已经是有序的 只需要为新插入节点找到一个合适的位置
        newRoot = self.length - 1
        
        # 如果当前节点被换到堆顶,则调整结束:如果当前节点数据大于父节点数据,那么就进行交换
        while newRoot and (self.heap[newRoot] > self.heap[(newRoot - 1) // 2]):
            self.heap[newRoot],self.heap[(newRoot-1)//2] = self.heap[(newRoot - 1) //2],self.heap[newRoot]
            newRoot = (newRoot-1)//2
            
    def heap_pop(self):
        # 输出堆顶元素:也就是self.heap[0]
        if len(self.heap) == 0:
            print('empty')
        else:
            ans = self.heap[0]
            # 将堆顶元素调换到最后  对堆顶进行调整
            self.heap[0],self.heap[-1] = self.heap[-1],self.heap[0]
            # 弹出元素
            self.heap.pop()
            # 大小减一
            self.length -= 1
            self.heapAdjust(0, self.length)
            print(ans)

    # 获取堆顶元素
    def heap_top(self):
        if len(self.heap) == 0:
            print('empty')
        else:
            print(self.heap[0])            

对一个数组数据进行最大堆的构建:从第一个非叶子节点进行heapAdjust调整

class MyHeap(object):
    def __init__(self):
        # 定义一个大根堆
        self.heap = []
        self.length = 0
        
    # 对堆的调整:堆是一个完全二叉树,通过找到第一个非叶子节点的位置,并调整该节点与左右孩子的大小关系,使其实现最大堆的性值:根节点的值大于左右孩子的值
    def heapAdjust(self, root, size):
    
        # NoLeaf ->非叶子节点
        largest = root
        
        # 左孩子位置
        left = root * 2 + 1
        
        # 右孩子位置
        right = root * 2 + 2
        
        # 寻找出 这三个位置的最大值所在位置
        if left < size and self.heap[left] > self.heap[largest]:
            largest = left
        if right < size and self.heap[right] > self.heap[largest]:
            largest = right
            
        # 判断是否满足最大堆性质
        if largest != root:
            self.heap[largest],self.heap[root] = self.heap[root],self.heap[largest]
            
            # 根节点调整完后,继续查看 以子节点为根节点的子树是否满足最大堆性质
            self.heapAdjust(largest,self.length)

    def heap_push(self, val):
        self.heap.append(val)
        self.length += 1
        
        # 插入节点的父节点到根节点已经是有序的 只需要为新插入节点找到一个合适的位置
        newRoot = self.length - 1
        
        # 如果当前节点被换到堆顶,则调整结束:如果当前节点数据大于父节点数据,那么就进行交换
        while newRoot and (self.heap[newRoot] > self.heap[(newRoot - 1) // 2]):
            self.heap[newRoot],self.heap[(newRoot-1)//2] = self.heap[(newRoot - 1) //2],self.heap[newRoot]
            newRoot = (newRoot-1)//2
            
    def heap_pop(self):
        # 输出堆顶元素:也就是self.heap[0]
        if len(self.heap) == 0:
            print('empty')
        else:
            ans = self.heap[0]
            # 将堆顶元素调换到最后  对堆顶进行调整
            self.heap[0],self.heap[-1] = self.heap[-1],self.heap[0]
            # 弹出元素
            self.heap.pop()
            # 大小减一
            self.length -= 1
            self.heapAdjust(0, self.length)
            print(ans)

    # 获取堆顶元素
    def heap_top(self):
        if len(self.heap) == 0:
            print('empty')
        else:
            print(self.heap[0]) 
            
    # 对一组数据进行最大堆的构建        
    def heapConstruct(self):
        # 构建大根堆: 从第一个非叶子结点开始调整即可
        for root in range((self.length - 1 - 1) // 2, -1, -1):
            self.heapify(root, self.length)

ACM模式的运行:

if __name__ == '__main__':

    A = MyHeap()
    operNum = int(input())
    # 执行相应的命令
    for i in range(operNum):
        order = input().split()
        if order[0] == 'push':
            A.heap_push(int(order[1]))
        elif order[0] == 'top':
            A.heap_top()
        elif order[0] == 'pop':
            A.heap_pop()

整个代码

class MyHeap(object):
    def __init__(self):
        # 定义一个大根堆
        self.heap = []
        self.length = 0
        
    # 对堆的调整:堆是一个完全二叉树,通过找到第一个非叶子节点的位置,并调整该节点与左右孩子的大小关系,使其实现最大堆的性值:根节点的值大于左右孩子的值
    def heapAdjust(self, root, size):
    
        # NoLeaf ->非叶子节点
        largest = root
        
        # 左孩子位置
        left = root * 2 + 1
        
        # 右孩子位置
        right = root * 2 + 2
        
        # 寻找出 这三个位置的最大值所在位置
        if left < size and self.heap[left] > self.heap[largest]:
            largest = left
        if right < size and self.heap[right] > self.heap[largest]:
            largest = right
            
        # 判断是否满足最大堆性质
        if largest != root:
            self.heap[largest],self.heap[root] = self.heap[root],self.heap[largest]
            
            # 根节点调整完后,继续查看 以子节点为根节点的子树是否满足最大堆性质
            self.heapAdjust(largest,self.length)

    def heap_push(self, val):
        self.heap.append(val)
        self.length += 1
        
        # 插入节点的父节点到根节点已经是有序的 只需要为新插入节点找到一个合适的位置
        newRoot = self.length - 1
        
        # 如果当前节点被换到堆顶,则调整结束:如果当前节点数据大于父节点数据,那么就进行交换
        while newRoot and (self.heap[newRoot] > self.heap[(newRoot - 1) // 2]):
            self.heap[newRoot],self.heap[(newRoot-1)//2] = self.heap[(newRoot - 1) //2],self.heap[newRoot]
            newRoot = (newRoot-1)//2
            
    def heap_pop(self):
        # 输出堆顶元素:也就是self.heap[0]
        if len(self.heap) == 0:
            print('empty')
        else:
            ans = self.heap[0]
            # 将堆顶元素调换到最后  对堆顶进行调整
            self.heap[0],self.heap[-1] = self.heap[-1],self.heap[0]
            # 弹出元素
            self.heap.pop()
            # 大小减一
            self.length -= 1
            self.heapAdjust(0, self.length)
            print(ans)

    # 获取堆顶元素
    def heap_top(self):
        if len(self.heap) == 0:
            print('empty')
        else:
            print(self.heap[0]) 
            
    # 对一组数据进行最大堆的构建        
    def heapConstruct(self):
        # 构建大根堆: 从第一个非叶子结点开始调整即可
        for root in range((self.length - 1 - 1) // 2, -1, -1):
            self.heapify(root, self.length)

if __name__ == '__main__':

    maxHeap = MyHeap()
    operNum = int(input())
    # 执行相应的命令
    for i in range(operNum):
        order = input().split()
        if order[0] == 'push':
            maxHeap.heap_push(int(order[1]))
        elif order[0] == 'top':
            maxHeap.heap_top()
        elif order[0] == 'pop':
            maxHeap.heap_pop()
全部评论

相关推荐

投递腾讯等公司10个岗位
点赞 评论 收藏
转发
2 收藏 评论
分享
牛客网
牛客企业服务