计算机等级考试—数组构建大顶队—东方仙盟

一步步构建大顶堆

1. 初始数组：A = [2, 8, 7, 1, 3, 5, 6, 4]
2. 堆的结构：数组长度为 8，完全二叉树的最后一个非叶子节点索引为⌊8/2⌋ - 1 = 3，所以我们从索引 3 开始，依次向上调整。

步骤 1：调整索引 3（值为 1）

• 子节点：索引 7（值为 4）
• 4 > 1 → 交换，数组变为：[2, 8, 7, 4, 3, 5, 6, 1]

步骤 2：调整索引 2（值为 7）

• 子节点：索引 5（值为 5）、索引 6（值为 6）
• 7 > 5 且 7 > 6 → 无需交换

步骤 3：调整索引 1（值为 8）

• 子节点：索引 3（值为 4）、索引 4（值为 3）
• 8 > 4 且 8 > 3 → 无需交换

步骤 4：调整索引 0（值为 2）

• 子节点：索引 1（值为 8）、索引 2（值为 7）
• 8 > 2 → 交换，数组变为：[8, 2, 7, 4, 3, 5, 6, 1]
• 继续调整索引 1（值为 2）：子节点索引 3（值为 4）、索引 4（值为 3）
• 4 > 2 → 交换，数组变为：[8, 4, 7, 2, 3, 5, 6, 1]
• 继续调整索引 3（值为 2）：子节点索引 7（值为 1）
• 2 > 1 → 无需交换

什么是大顶堆（Max Heap）

大顶堆是一种完全二叉树结构，满足两个核心条件：

1. 结构上：是一棵完全二叉树，即除了最后一层，其他层的节点都被填满，且最后一层的节点尽量靠左排列。
2. 堆性质：每个父节点的值大于或等于它的所有子节点的值，因此堆顶（根节点）是整个堆中的最大值。

在数组表示中：

• 对于索引为i的节点：
  • 左子节点索引：2i + 1
  • 右子节点索引：2i + 2
  • 父节点索引：⌊(i-1)/2⌋

二、用 Mermaid 图展示大顶堆构建过程

初始数组：A = [2, 8, 7, 1, 3, 5, 6, 4]

1. 初始完全二叉树（未满足堆性质）

graph TD A((2)) --> B((8)) A --> C((7)) B --> D((1)) B --> E((3)) C --> F((5)) C --> G((6)) D --> H((4))

2. 调整最后一个非叶子节点（索引 3，值为 1）

graph TD A((2)) --> B((8)) A --> C((7)) B --> D((4)) B --> E((3)) C --> F((5)) C --> G((6)) D --> H((1))

（交换 1 和 4，使子节点不大于父节点）

3. 调整索引 2（值为 7）

graph TD A((2)) --> B((8)) A --> C((7)) B --> D((4)) B --> E((3)) C --> F((5)) C --> G((6)) D --> H((1))

（7 ≥ 5 且 7 ≥ 6，无需交换）

4. 调整索引 1（值为 8）

graph TD A((2)) --> B((8)) A --> C((7)) B --> D((4)) B --> E((3)) C --> F((5)) C --> G((6)) D --> H((1))

（8 ≥ 4 且 8 ≥ 3，无需交换）

5. 调整根节点（索引 0，值为 2）

graph TD A((8)) --> B((2)) A --> C((7)) B --> D((4)) B --> E((3)) C --> F((5)) C --> G((6)) D --> H((1))

（交换 2 和 8，使根节点为最大值）

6. 继续调整索引 1（值为 2）

graph TD A((8)) --> B((4)) A --> C((7)) B --> D((2)) B --> E((3)) C --> F((5)) C --> G((6)) D --> H((1))

（交换 2 和 4，使父节点值≥子节点）

最终大顶堆（数组：[8, 4, 7, 2, 3, 5, 6, 1]）

graph TD A((8)) --> B((4)) A --> C((7)) B --> D((2)) B --> E((3)) C --> F((5)) C --> G((6)) D --> H((1))

阿雪技术观

在科技发展浪潮中，我们不妨积极投身技术共享。不满足于做受益者，更要主动担当贡献者。无论是分享代码、撰写技术博客，还是参与开源项目维护改进，每一个微小举动都可能蕴含推动技术进步的巨大能量。东方仙盟是汇聚力量的天地，我们携手在此探索硅基生命，为科技进步添砖加瓦。

Hey folks, in this wild tech - driven world, why not dive headfirst into the whole tech - sharing scene? Don't just be the one reaping all the benefits; step up and be a contributor too. Whether you're tossing out your code snippets, hammering out some tech blogs, or getting your hands dirty with maintaining and sprucing up open - source projects, every little thing you do might just end up being a massive force that pushes tech forward. And guess what? The Eastern FairyAlliance is this awesome place where we all come together. We're gonna team up