合并两个二叉最大堆。

堆是基于树的数据结构，通常用于实现优先队列。它们允许高效地访问最大或最小元素。有时，我们必须将两个堆合并成一个包含来自两个堆的所有元素的单一合并堆。这允许实现跨越多个堆的优先队列。

本文将探讨如何合并两个二叉最大堆。最大堆的属性是每个节点的值都大于或等于其子节点的值。合并两个这样的堆涉及将其元素重新组合成一个新的最大堆，该堆包含来自两个原始堆的节点。我们将使用一个简单的 O(n) 算法，该算法最优地合并结构和元素来创建组合堆。

什么是堆？

堆是一种特殊化的树数据结构，它满足“堆属性”——每个节点的键或值大于或等于（或小于或等于）其子节点的键。

一种思考堆的方式是将其视为“部分有序二叉树”。这意味着树是二叉的（每个节点最多有两个子节点），并且节点的顺序基于堆属性，但整体结构不是从上到下完全有序的。

堆通常使用数组来实现，方法是将树结构映射到索引位置。根节点存储在数组索引 1 处，节点 i 的子节点存储在索引 2*i 和 2*i+1 处。

与二叉搜索树不同，堆不保证“兄弟节点”（同一级别的节点）之间的排序。唯一的保证是父节点和子节点之间的关系。

堆在实现优先队列时非常有用，因为它们允许快速访问最小或最大元素，同时还能快速插入和删除部分。

因此，总而言之，堆是一种存储在数组中的部分有序二叉树，它提供对极值元素的有效访问以及灵活的插入/删除。松散的结构与堆属性相结合，赋予了堆强大的功能和受欢迎的程度。

二叉堆和二叉最大堆？

二叉堆是一种堆数据结构，具有两个附加约束——树是完全二叉树，并且树的所有级别都已填充，除了最后一个级别可能未满。

成为完全二叉树意味着除了最后一级外，所有树级别都已填充。上一级的节点都从左到右填充。

完全二叉树的这一属性允许使用数组紧凑地表示二叉堆，如前所述。第一个节点存储在数组索引 1 处，并且索引 i 处节点的左子节点和右子节点分别存储在 2*i 和 2*i+1 处。

二叉最大堆是具有附加最大堆属性的二叉堆——每个节点的键大于或等于其子节点的键。

因此，在二叉最大堆中，最大的键始终位于根节点。以任何节点为根的子树也遵循最大堆属性。

这使得可以快速访问最大值并进行高效操作，如 extract-max、insert 等。二叉最大堆是实现优先队列的流行方法。

总而言之，二叉最大堆结合了三个属性

1. 它是一棵二叉树
2. 它是一棵完全二叉树
3. 它满足最大堆属性

这种组合使得能够实现高效的优先队列。最大元素易于访问，插入和提取需要 O(log n) 时间，内存使用紧凑。

合并两个二叉最大堆

目标是将两个单独的二叉最大堆合并成一个新的二叉最大堆，该堆包含来自两个堆的所有元素。

我们希望同时合并结构和值。合并后的堆应遵循最大堆属性——其元素应按值排序，最大元素位于根节点。

该算法涉及递归地合并根节点对

1. 创建一个新的空最大堆来存储最终合并后的堆。
2. 将第一个堆的根节点添加到合并后的堆中。
3. 添加第二个堆的根节点。比较新添加的两个根节点的值，如果需要则交换它们，以便值较高的节点位于合并后的根节点。
4. 取第一个堆的根节点的左子节点和第二个堆的根节点的左子节点。将它们都添加到合并后的堆中，并通过比较值来修复顺序。
5. 类似地，添加两个堆根节点的右子节点，并在需要时修复顺序。
6. 递归地重复步骤 2-5，比较和合并来自增加深度的子树的根节点。

通过递归地比较和在合并两个节点时修复顺序，我们可以合并结构和节点值，以在最终合并的堆中保留最大堆排序。

合并包含 n 个元素的两个堆的时间复杂度为 O(n)。该算法渐近最优。

输出

说明

1. 定义 merge_heaps() 函数，该函数接收两个堆（heap1 和 heap2）作为输入。
2. 创建一个 merged_heap 列表，将 heap1 和 heap2 的所有元素连接成一个单一列表。这包含了必须进入最终合并堆的所有元素。
3. 定义一个辅助的 heapify() 函数来修复存储在数组 arr 中的堆中任何违反最大堆属性的情况。它接收数组、长度 n 和当前索引 i。
4. 在 heapify() 中，首先假设当前节点 i 是最大的。将其与数组中的左子节点和右子节点索引进行比较。如果任何子节点的值更大，则将 largest 更新为子节点索引。
5. 如果 largest 与原始 I 不同，则交换数组中 I 和 largest 的值。这会将较大的元素移到上方以恢复最大堆属性。
6. 递归调用 heapify 在新索引 i 处修复其下方的子树。
7. 初始化 n 为 merged_heap 的长度。从前半部分的最后一个非叶节点开始向后遍历，并在每个节点上调用 heapify。这会自底向上构建堆。
8. 返回完全合并并已堆化的数组作为结果。
9. 为了测试该算法，定义两个样本输入堆 heap1 和 heap2。
10. 调用 merge_heaps() 处理这些输入堆。
11. 打印最终合并的堆。我们可以验证它是否遵循了最大堆排序。

更有效的方法

此方法在合并时使用 PriorityQueue 作为中间数据结构。PriorityQueue 充当最大堆或最小堆（默认情况下为最小堆）。

通过推送负数，我们翻转所有值，因此 PriorityQueue 现在充当最大堆，始终将最大元素保留在顶部。

我们使用 PriorityQueue 的堆插入和 extract-max 操作，逐个高效地合并两个输入的max堆。

最后，我们将元素从 PriorityQueue 弹出到列表中，以返回具有正确元素排序的合并后的最大堆。

合并具有总共 n 个元素的两个堆的时间复杂度为 O(n)。

使用 PriorityQueue 避免了在合并后的数组上编写自定义 heapify 过程。这使得逻辑更简单。

空间复杂度为 O(n)，用于包含 n 个元素的合并数组，以及 O(n)，用于中间 PriorityQueue。

输出

说明

1. 从 queue 库导入 PriorityQueue 类
2. 定义 merge_heaps 函数，接收两个输入堆作为参数
3. 初始化一个空的 PriorityQueue 对象，名为 pq
4. 循环遍历第一个输入堆 heap1 的所有元素
5. 对于使用 PriorityQueue 的最大堆，通过 pq.put(-item) 将每个元素的负值推入 pq
6. 类似地，循环遍历第二个输入堆 heap2，并将元素的负值推入 pq
7. 初始化一个空列表 merged_heap 来存储最终合并的堆
8. 将元素从 pq 弹出到 merged_heap。再次使用负数，这样最大元素就是根节点
9. 返回最终合并的最大堆

10-12. 定义输入堆并打印合并后的堆