《数据结构（邓俊辉）》学习笔记：完全二叉堆——插入与上滤（第04章）

文章目录

• 1. 上滤
• 2. 实例
• 3. 实现
• 4. 效率

1. 上滤

让我们随后掌握在完全二叉堆中高效地插入一个新的元素这一过程的核心技巧被称为上滤过程。

为了在完全二叉堆中加入一个新的元素e，在这种情况下我们需要将它视为末尾元素，并将其直接放置于对应的向量中。需要注意的是，在这种情况下使用的是标准的向量数据结构。

请记住：虽然在逻辑层面我们可以将优先级队列视为一棵完全二叉树，在物理层面它始终是一个不容置疑的向量；在物理层面上增加一个末元素相当于在这棵完全二叉树底层向空缺的部分拓展一个新的节点

观察到，在向量中以末元素形式加入新的条目所带来的好处是可以维持完全二叉堆的结构性特征。此外，如果同时能够保持所谓的堆序性，则我们的目标也就达成了。然而实际上，在新节点被引入后，堆序性可能无法持续维持。

然而即使如此情况也不会太糟糕。具体情况而言仅限于新插入的那个节点与其父节点之间可能出现违反堆序性的情况即该节点必须满足其数值大于父节点。

一旦识别出问题的根本所在, 自然随之而来的就是找到解决问题的方法了。实际上