3.4 堆（最大堆、最小堆、优先队列）

文档摘要

3.4 堆（最大堆、最小堆、优先队列） 3.4 堆（最大堆、最小堆、优先队列） 3.4.1 堆的定义堆是一种特殊的树形数据结构，它满足以下两个关键性质：结构性：堆总是一棵完全二叉树。这意味着除了最后一层外，树的每一层都被完全填满，并且最后一层的所有节点都尽可能地集中在左侧。堆序性：堆中的每个节点的值都必须满足特定的顺序关系，具体取决于堆的类型：最大堆：对于每个节点，其值都大于或等于其子节点的值。这意味着根节点的值是堆中最大的。最小堆：对于每个节点，其值都小于或等于其子节点的值。这意味着根节点的值是堆中最小的。 3.4.2 堆的表示由于堆是完全二叉树，因此通常使用数组来高效地表示它。对于数组中索引为的节点：其左子节点的索引为。其右子节点的索引为。