Python 堆指南

介绍

想象一下一个繁忙的机场，每分钟都有航班起飞和降落。 正如空中交通管制员根据紧急程度确定航班的优先级一样，堆帮助我们根据特定标准管理和处理数据，确保最“紧急”或“重要”的数据始终可以在顶部访问。

在本指南中，我们将踏上从头开始理解堆的旅程。 我们将首先揭开堆是什么及其固有属性的神秘面纱。 从这里开始，我们将深入研究 Python 自己的堆实现，即 heapq 模块，并探索其丰富的功能。 因此，如果您想知道如何有效地管理经常需要最高（或最低）优先级元素的动态数据集，那么您就很高兴了。

什么是堆？

在深入了解堆的使用之前，您需要了解的第一件事是 什么是堆。 堆作为基于树的动力源在数据结构领域中脱颖而出，尤其擅长 维持秩序和等级制度。 虽然对于未经训练的人来说，它可能类似于二叉树，但其结构和管理规则的细微差别明显使其与众不同。

堆的定义特征之一是它的本质是 完整的二叉树。 这意味着树的每一层（也许除了最后一层）都被完全填满。 在最后一个级别中，节点从左到右填充。 这种结构确保可以使用数组或列表有效地表示和操作堆，数组中每个元素的位置反映其在树中的位置。

然而，堆的真正本质在于它 订购。 在 最大堆，任何给定节点的值都超过或等于其子节点的值，将最大元素定位在根的右侧。 另一方面，一个 最小堆 遵循相反的原则：任何节点的值都小于或等于其子节点的值，确保最小的元素位于根。

随着我们的进展，我们将更深入地了解堆的这些固有属性如何实现高效操作以及 Python 如何 heapq 模块将堆无缝集成到我们的编码工作中。

堆的特征和属性

堆以其独特的结构和排序原则，带来了一系列独特的特征和属性，使它们在各种计算场景中具有无价的价值。

首先也是最重要的，堆是 本质上有效。 它们基于树的结构，特别是完整的二叉树格式，确保可以在对数时间内执行插入和提取优先级元素（最大或最小）等操作，通常 O（log n）。 这种效率对于需要频繁访问优先级元素的算法和应用程序来说是一个福音。

堆的另一个值得注意的属性是它们 记忆效率。 由于堆可以使用数组或列表来表示，而不需要显式指向子节点或父节点的指针，因此它们可以节省空间。 数组中每个元素的位置与其在树中的位置相对应，从而允许可预测且直接的遍历和操作。

堆的排序属性，无论是最大堆还是最小堆，都确保 根始终拥有最高优先级的元素。 这种一致的顺序允许快速访问最优先的元素，而无需搜索整个结构。

此外，堆是 多才多艺。 虽然二元堆（每个父堆最多有两个子堆）是最常见的，但堆可以概括为具有两个以上的子堆，称为 d 元堆。 这种灵活性允许根据特定用例和性能要求进行微调。

最后，堆是 自我调整。 每当添加或删除元素时，结构都会重新排列以保持其属性。 这种动态平衡确保堆始终针对其核心操作保持优化。

随着我们深入研究 Python 的实现和实际应用，堆的真正潜力将展现在我们面前。

堆的类型

并非所有堆都是一样创建的。 根据堆的顺序和结构属性，堆可以分为不同的类型，每种类型都有自己的应用程序和优点。 两个主要类别是 最大堆 和 最小堆.

最显着的特点是 最大堆 是任何给定节点的值大于或等于其子节点的值。 这确保了堆中最大的元素始终位于根部。 当需要频繁访问最大元素时（例如在某些优先级队列实现中），这种结构特别有用。

最大堆的对应项，a 最小堆 确保任何给定节点的值小于或等于其子节点的值。 这会将堆的最小元素定位在根部。 在最小元素至关重要的情况下（例如在处理实时数据处理的算法中），最小堆非常宝贵。

除了这些主要类别之外，还可以根据其分支因子来区分堆：

虽然二叉堆是最常见的，每个父节点最多有两个子节点，但堆的概念可以扩展到具有两个以上子节点的节点。 在一个 d-ary堆, 每个节点最多有 d 孩子们。 这种变化可以针对特定场景进行优化，例如降低树的高度以加速某些操作。

二项堆 是一组递归定义的二项式树。 二项式堆用于优先级队列实现并提供高效的合并操作。

以著名的斐波那契数列命名 斐波那契堆 与二项堆或二项式堆相比，为许多操作提供更好的摊销运行时间。 它们在网络优化算法中特别有用。

Python 的堆实现 – 堆 模块

Python 提供了一个用于堆操作的内置模块 – heapq 模块。 该模块提供了一系列与堆相关的函数，允许开发人员将列表转换为堆并执行各种堆操作，而无需自定义实现。 让我们深入了解该模块的细微差别以及它如何为您带来堆的强大功能。

heapq 模块不提供不同的堆数据类型。 相反，它提供了适用于常规 Python 列表的函数，将它们转换并视为 二叉堆.

这种方法既节省内存，又与 Python 现有的数据结构无缝集成。

这意味着 堆被表示为列表 in heapq。 这种表示的优点在于它的简单性——从零开始的列表索引系统充当隐式二叉树。 对于位置处的任何给定元素 i， 它的：

• 左孩子处于位置 2*i + 1
• 右孩子处于位置 2*i + 2
• 父节点位于位置 (i-1)//2

这种隐式结构确保不需要单独的基于节点的二叉树表示，从而使操作简单明了并且内存使用量最少。

值得注意的是 heapq 模块 默认创建最小堆。 这意味着最小的元素始终位于根（或列表中的第一个位置）。 如果您需要最大堆，则必须通过将元素乘以来反转顺序 -1 或使用自定义比较函数。

Python的 heapq 模块提供了一套函数，允许开发人员对列表执行各种堆操作。

在下面的部分中，我们将深入研究每个基本操作，探索它们的机制和用例。

如何将列表转换为堆

heapify() 函数是许多与堆相关的任务的起点。 它需要一个可迭代对象（通常是一个列表）并就地重新排列其元素以满足最小堆的属性：

import heapq data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
heapq.heapify(data)
print(data)

这将输出一个重新排序的列表，表示有效的最小堆：

[1, 1, 2, 3, 3, 9, 4, 6, 5, 5, 5]

如何向堆添加元素

heappush() 函数允许您将新元素插入堆中，同时保持堆的属性：

import heapq heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
print(heap)

运行代码将为您提供维护最小堆属性的元素列表：

[3, 5, 7]

如何从堆中删除并返回最小的元素

heappop() 函数从堆中提取并返回最小元素（最小堆中的根）。 删除后，它确保列表仍然是有效的堆：

import heapq heap = [1, 3, 5, 7, 9]
print(heapq.heappop(heap))
print(heap)

这将输出最小的元素和剩余的列表：

1
[3, 7, 5, 9]

在这里， 1 是最小的元素 heap，即使我们删除了剩余的列表，仍然保留了堆属性 1.

如何推送新项目并弹出最小的项目

heappushpop() 函数是一个组合操作，它将一个新项目推送到堆上，然后弹出并返回堆中最小的项目：

import heapq heap = [3, 5, 7, 9]
print(heapq.heappushpop(heap, 4)) print(heap)

这将输出 3，最小的元素，并打印出新的 heap 现在包括的列表 4 在维护堆属性的同时：

3
[4, 5, 7, 9]

如何替换最小的项目并推送新项目

heapreplace() 函数弹出最小的元素并将新元素推送到堆上，所有这些都通过一个高效的操作完成：

import heapq heap = [1, 5, 7, 9]
print(heapq.heapreplace(heap, 4))
print(heap)

这打印 1，最小元素，列表现在包含 4 个元素并维护堆属性：

1
[4, 5, 7, 9]

在 Python 堆中查找多个极端

nlargest(n, iterable[, key]) 和 nsmallest(n, iterable[, key]) 函数旨在从可迭代对象中检索多个最大或最小元素。 当您只需要几个极值时，它们比对整个可迭代进行排序更有效。 例如，假设您有以下列表，并且您想要在列表中查找三个最小值和三个最大值：

data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

在这里， nlargest() 和 nsmallest() 函数可以派上用场：

import heapq data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(heapq.nlargest(3, data)) print(heapq.nsmallest(3, data)) 

这将为您提供两个列表 - 一个包含三个最大值，另一个包含三个最小值 data 列表：

[9, 6, 5]
[1, 1, 2]

如何构建自定义堆

虽然Python的 heapq 模块提供了一组强大的工具来处理堆，但在某些情况下默认的最小堆行为可能不够。 无论您是想要实现最大堆还是需要基于自定义比较函数操作的堆，构建自定义堆都可以是答案。 让我们探讨如何根据特定需求定制堆。

使用实现最大堆 heapq

默认情况下， heapq 创建 最小堆。 然而，通过一个简单的技巧，您可以使用它来实现最大堆。 这个想法是通过将元素乘以来反转元素的顺序 -1 在将它们添加到堆之前：

import heapq class MaxHeap: def __init__(self): self.heap = [] def push(self, val): heapq.heappush(self.heap, -val) def pop(self): return -heapq.heappop(self.heap) def peek(self): return -self.heap[0]

通过这种方法，最大的数字（就绝对值而言）变成最小的，从而允许 heapq 函数来维护最大堆结构。

具有自定义比较函数的堆

有时，您可能需要一个不仅仅根据元素的自然顺序进行比较的堆。 例如，如果您正在处理复杂的对象或具有特定的排序标准，则自定义比较功能就变得至关重要。

为此，您可以将元素包装在重写比较运算符的帮助器类中：

import heapq class CustomElement: def __init__(self, obj, comparator): self.obj = obj self.comparator = comparator def __lt__(self, other): return self.comparator(self.obj, other.obj) def custom_heappush(heap, obj, comparator=lambda x, y: x < y): heapq.heappush(heap, CustomElement(obj, comparator)) def custom_heappop(heap): return heapq.heappop(heap).obj

通过此设置，您可以定义任何自定义比较器函数并将其与堆一起使用。

结论

堆为许多操作提供可预测的性能，使其成为基于优先级的任务的可靠选择。 但是，必须考虑当前应用程序的具体要求和特征。 在某些情况下，调整堆的实现甚至选择替代数据结构可能会产生更好的实际性能。

正如我们所了解的，堆不仅仅是另一种数据结构。 它们代表了效率、结构和适应性的融合。 从它们的基本属性到它们在 Python 中的实现 heapq 模块中，堆为无数计算挑战提供了强大的解决方案，尤其是那些以优先级为中心的计算挑战。

• SEO 支持的内容和 PR 分发。 今天得到放大。
• PlatoData.Network 垂直生成人工智能。 赋予自己力量。 访问这里。
• 柏拉图爱流。 Web3 智能。 知识放大。 访问这里。
• 柏拉图ESG。 碳， 清洁科技, 能源， 环境， 太阳能， 废物管理。 访问这里。
• 柏拉图健康。 生物技术和临床试验情报。 访问这里。
• Sumber: https://stackabuse.com/guide-to-heaps-in-python/