如何检查给定数组是否代表堆？

二叉堆是一种有用的数据结构，可以使用数组来实现。它们可以高效地访问数据集中最小或最大的元素。二叉堆通常用于实现优先级队列和图算法，如 Dijkstra 算法。

为了使用二叉堆，验证给定数组是否准确地表示了二叉堆结构非常重要。本文将探讨一种 O(N) 算法来检查数组是否对应于有效的二叉最大堆或最小堆。这涉及到验证两个关键属性——完全二叉树结构和堆序属性。

二叉堆通常用数组表示，数组镜像了完全二叉树的结构。这提供了一种高效存储元素同时保持父子节点关系的方法。在使用数组作为二叉堆之前，验证它是否表示一个有效的堆很有用。本文将介绍一种 O(N) 算法，用于检查数组是否满足作为二叉最大堆或最小堆所需的属性。我们将讨论如何检查完全二叉树结构和验证堆序属性。

什么是数组？

数组是一种数据结构，它在内存中按顺序存储一组元素。每个元素都可以通过其索引直接访问，这使得访问和修改元素变得高效。

数组的大小是固定的，在创建时设置。数组中的元素可以是任何数据类型，如整数、字符串、对象等。同一数组中的所有元素必须是相同的数据类型。

数组对于存储和访问顺序数据、按索引查找元素以及高效地遍历元素很有用。然而，在末尾以外的任何位置添加或删除元素都需要移动内存中的其他元素。

二叉堆通常使用数组来实现，因为数组索引与堆的树形结构对齐。父子关系可以通过索引数学推导出来。这使得堆结构的遍历、交换和维护变得高效。

什么是堆？

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

堆可以高效地访问最小或最大元素，从而以常数时间检索极端值。堆通常使用数组来实现。

堆属性可以高效地进行元素的插入和删除，同时保持顺序。元素可以插入到末尾，然后向上或向下冒泡以满足堆属性。删除总是从根节点进行。

当需要反复查找最小值或最大值时，堆很有用，例如优先级队列。它们在保持最大/最小值可访问的同时，提供高效的 O(log n) 插入和删除。

二叉堆每个父节点最多有两个子节点，是二叉堆结构的一种特定类型。二叉堆常用于实现优先级队列和图算法。

堆的属性

• 堆是完全二叉树——除了最后一层外，所有层都已填满，并且节点从左到右添加。
• 堆满足堆属性——对于最大堆，每个节点大于或等于其子节点；对于最小堆，每个节点小于或等于其子节点。
• 元素的插入和删除会维护堆属性。
• 根节点包含最大值或最小值。
• 最大/最小值可以在常数 O(1) 时间内访问。

数组的属性

• 数组由连续的内存位置组成，用于存储元素
• 数组中的元素在内存中按顺序存储
• 数组的大小在创建时固定
• 可以在常数 O(1) 时间内通过索引直接访问数组元素
• 数组中的所有元素必须是相同的数据类型
• 除了末尾以外添加/删除元素效率低下，因为它需要移动

通过利用数组的这些属性，二叉堆可以有效地表示为数组。索引映射到树结构。这允许轻松遍历和维护堆结构。

检查步骤

要检查数组是否代表二叉堆，我们需要验证两个关键属性

1. 数组必须表示一个完全二叉树结构

完全二叉树填满除最后一层之外的所有层，节点从左到右填充。我们可以遍历数组并使用这些规则检查树结构

• 根节点位于索引 0
• 对于索引 i 的任何节点
  • 其左子节点位于索引 2*i + 1
  • 其右子节点位于索引 2*i + 2

我们遍历数组，使用公式计算每个节点的子节点索引。如果预期子节点丢失或索引不匹配，则树结构无效。

例如，对于索引为 1 的节点，其左子节点应为 2*1 + 1 = 3，右子节点应为 2*1 + 2 = 4。如果任何预期的子节点越界或不存在，则结构不是完全二叉树。

我们完成一次遍历来验证树的形状。如果发现任何违反之处，我们可以得出结论，该数组不代表二叉堆。

2. 堆属性必须对每个节点都成立。

对于最大堆，堆属性意味着每个节点大于或等于其所有子节点；对于最小堆，每个节点小于或等于其所有子节点。

我们再次遍历数组，将每个节点与其子节点进行比较。我们使用上述公式通过计算出的子节点索引访问数组。如果节点值小于任何子节点（对于最大堆），则属性被违反。

例如，如果 array[2] < array[5]（第一个子节点）或 array[2] < array[6]（第二个子节点），则存在违反。

如果发现任何节点不满足堆属性，则该数组不能代表有效的二叉堆。

我们必须遍历整个数组，在每个节点上检查堆属性。如果两次遍历都完成且未发现任何违反，则数组满足所有要求，代表一个有效的二叉最大堆或最小堆。

因此，总而言之，我们遍历一次，检查结构，然后再遍历一次，验证堆属性。此算法以 O(N) 时间验证数组是否为二叉堆。

Python 程序

输出

说明

1. 定义 isMaxHeap() 函数，该函数接受数组 (arr) 和元素数量 (n) 作为输入。
2. 计算最后一个内部节点的索引为 int((n-2)/2)。我们将在该索引处循环，因为堆的属性必须对所有内部节点都成立。
3. 从根节点索引 0 开始，到一个 for 循环，直到最后一个内部节点索引。
4. 使用以下公式计算当前节点 i 的左子节点和右子节点的索引
   • 左子节点索引 = 2*i + 1
   • 右子节点索引 = 2*i + 2

1. 检查左子节点是否大于当前节点
2. if arr[2*i + 1] > arr[i]
3. 如果是，则属性被违反，因此返回 False。
4. 检查右子节点是否存在 (2*i + 2 < n) 并且它是否大于当前节点：
5. if (2*i + 2 < n and arr[2*i + 2] > arr[i])
6. 如果是，则属性被违反，因此返回 False。
7. 如果循环在不返回 False 的情况下完成，则最大堆属性对所有内部节点都成立。返回 True。
8. 在驱动代码中调用 isMaxHeap() 并打印返回值。

因此，总而言之，我们从根节点遍历到最后一个内部节点，使用公式访问子节点并在每一步验证堆序属性。如果发现任何违反，将立即返回 False。

时间复杂度为 O(N)，因为我们每个节点只访问一次。