在 Python 中获取最大堆
Jesse John
2023年1月30日
堆是实现优先级队列的首选数据结构。与二叉搜索树不同，堆不是完全有序的；兄弟姐妹或堂兄弟之间没有明确的顺序。
在 Python 中，heapq 模块实现了堆队列算法。然而，heapq 仅提供 Min Heap 实现，其中任何父节点的值小于或等于其子节点的值。
主函数 heappop() 返回堆的最小元素。
本文将讨论通过将 heapq 与一些自定义代码结合来在 Python 中实现最大堆行为。
在 Python 中使用数字获取最大堆
处理数字时最常见的策略是将列表的元素乘以 -1。heapq 函数可以处理堆。
弹出最小值后，我们需要再次将输出乘以 -1 以获得最大值。
示例代码：
# import the heapq module.
import heapq
# Max Heap With Numbers
# Create a list.
x = [5, 4, 3, 6, 8, 7, 2, 1]
# Print the list.
print(x)
# Multiply elements by -1.
x_inv = [-1 * i for i in x]
print(x_inv)
# Make the heap.
heapq.heapify(x_inv)
# Pop the maximum value.
# RUN ONE LINE AT A TIME.
-1 * heapq.heappop(x_inv)
-1 * heapq.heappop(x_inv)
-1 * heapq.heappop(x_inv)
输出：
print(x)
[5, 4, 3, 6, 8, 7, 2, 1]
print(x_inv)
[-5, -4, -3, -6, -8, -7, -2, -1]
-1 * heapq.heappop(x_inv)
Out[8]: 8
-1 * heapq.heappop(x_inv)
Out[9]: 7
-1 * heapq.heappop(x_inv)
Out[10]: 6
在 Python 中使用元组获取最大堆
我们可能想用元组而不是数字来实现一个优先级队列。由于 Python 的元组是不可变的，这对将优先级数乘以 -1 的任务是一个挑战。
解决方案在于首先将每个元组转换为列表，将这些子列表的第一个元素修改为 -1，将它们转换回元组，同时使用这些元组创建一个新列表。然后使用 heapify() 将新列表转换为堆。
要弹出最大值，我们在堆上使用 heappop()，将元组转换为列表，修改第一个元素以获得正值，然后将列表转换回元组。
示例代码：
# Max Heap With Tuples
# Make a list of tuples.
l = [(1, "A"), (5, "B"), (3, "C"), (7, "D"), (6.5, "E")]
# View the list.
l
# Create an empty list to hold modified tuples.
l_max = []
# Populate the list with modified tuples.
for i in range(len(l)):
j = list(l[i])
j[0] = -1 * j[0]
l_max.append(tuple(j))
# View the modified list.
l_max
# Create the min heap.
heapq.heapify(l_max)
# View the min-heap.
l_max
# Create a function that uses meappop and
# changes the number back to a positive value.
def maxpop(mh):
l = list(heapq.heappop(mh))
l[0] = -1 * l[0]
return tuple(l)
# Test the values popped by the maxpop.
# RUN ONE LINE AT A TIME.
maxpop(l_max)
maxpop(l_max)
maxpop(l_max)
输出：
l
Out[15]: [(1, 'A'), (5, 'B'), (3, 'C'), (7, 'D'), (6.5, 'E')]
l_max
Out[14]: [(-1, 'A'), (-5, 'B'), (-3, 'C'), (-7, 'D'), (-6.5, 'E')]
heapq.heapify(l_max)
l_max
Out[17]: [(-7, 'D'), (-6.5, 'E'), (-3, 'C'), (-5, 'B'), (-1, 'A')]
maxpop(l_max)
Out[19]: (7, 'D')
maxpop(l_max)
Out[20]: (6.5, 'E')
maxpop(l_max)
Out[21]: (5, 'B')
其他需要的堆函数可以使用相同的技术来实现。
参考
参见 Python 的 heapq 模块 的文档以了解更多细节和例子。
Python 开发团队决定不实现最大堆函数。你可以在此处阅读功能请求和响应。
作者： Jesse John
Jesse is passionate about data analysis and visualization. He uses the R statistical programming language for all aspects of his work.