上一节:
下一节:

  Python - 数据结构之堆

  • 简述

    堆是一种特殊的树结构，其中每个父节点都小于或等于其子节点。然后它被称为最小堆。如果每个父节点都大于或等于其子节点，则称为最大堆。实现优先级队列非常有用，其中具有较高权重的队列项目在处理中具有更高的优先级。
    在我们的网站上可以找到关于堆的详细讨论。如果您是堆数据结构的新手，请先学习它。在本章中，我们将看到使用 python 实现堆数据结构。

  • 创建堆

    使用 python 的内置库 heapq 创建一个堆。该库具有对堆数据结构进行各种操作的相关功能。下面是这些函数的列表。
    • heapify− 此函数将常规列表转换为堆。在生成的堆中，最小的元素被推到索引位置 0。但其余数据元素不一定是排序的。
    • heappush− 该函数在不改变当前堆的情况下向堆中添加一个元素。
    • heappop− 该函数返回堆中最小的数据元素。
    • heapreplace− 该函数用函数中提供的新值替换最小的数据元素。

  • 创建堆

    通过简单地使用带有 heapify 函数的元素列表来创建堆。在下面的示例中，我们提供了一个元素列表，heapify 函数重新排列元素，将最小元素带到第一个位置。

    例子

    
import heapq

H = [21,1,45,78,3,5]
# Use heapify to rearrange the elements
heapq.heapify(H)
print(H)

    输出

    执行上述代码时，会产生以下结果 - 
    
[1, 3, 5, 78, 21, 45]

  • 插入堆

    将数据元素插入堆总是会在最后一个索引处添加元素。但是您可以再次应用 heapify 函数以将新添加的元素带到第一个索引，前提是它的值最小。在下面的示例中，我们插入数字 8。

    例子

    
import heapq

H = [21,1,45,78,3,5]
# Covert to a heap
heapq.heapify(H)
print(H)

# Add element
heapq.heappush(H,8)
print(H)

    输出

    执行上述代码时，会产生以下结果 - 
    
[1, 3, 5, 78, 21, 45]
[1, 3, 5, 78, 21, 45, 8]

  • 从堆中移除

    您可以使用此函数删除第一个索引处的元素。在下面的示例中，该函数将始终删除索引位置 1 处的元素。

    例子

    
import heapq

H = [21,1,45,78,3,5]
# Create the heap

heapq.heapify(H)
print(H)

# Remove element from the heap
heapq.heappop(H)

print(H)

    输出

    执行上述代码时，会产生以下结果 - 
    
[1, 3, 5, 78, 21, 45]
[3, 21, 5, 78, 45]

  • 在堆中替换

    堆替换函数总是删除堆中最小的元素，并将新的传入元素插入到某个不按任何顺序固定的位置。

    例子

    
import heapq

H = [21,1,45,78,3,5]
# Create the heap

heapq.heapify(H)
print(H)

# Replace an element
heapq.heapreplace(H,6)
print(H)

    输出

    执行上述代码时，会产生以下结果 - 
    
[1, 3, 5, 78, 21, 45]
[3, 6, 5, 78, 21, 45]
上一节:
下一节: