题解 | #【模板】堆：一组数据实现最大堆 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()