❮ Python 数据结构 搜索树

Python 数据结构 图表 ❯

Python - 堆

更新于 2024/1/28 21:46:00

堆是一种特殊的树结构，其中每个父节点都小于或等于其子节点。 然后它被称为最小堆。 如果每个父节点都大于或等于它的子节点，那么它被称为最大堆。 实现优先级队列非常有用，其中权重较高的队列项在处理中具有更高的优先级。

在本章中，我们将看到使用 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]

❮ Python 数据结构 搜索树

Python 数据结构 图表 ❯