数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究对称最小最大堆
对称最小最大堆 (SMMH) 定义为一棵完全二叉树，其中除根节点外，每个节点都恰好包含一个元素。SMMH 的根节点可以为空，SMMH 中节点的总数为 m + 1，其中 m 是元素的数量。
设 y 为 SMMH 中的任意节点。设 elements(y) 为以 y 为根的子树中的元素，但不包括 y 中的元素（如果有）。假设 elements(y) j= ∅。y 满足以下属性
- y 的左孩子在 elements(y) 中具有最小元素。
- y 的右孩子（如果有）在 elements(y) 中具有最大元素。
图 1 显示了一个包含 12 个元素的 SMMH 示例。
当 y 表示值为 81 的节点时，elements(y) = {7, 15, 31, 41}；y 的左孩子在 elements(y) 中具有最小元素 6；y 的右孩子在 elements(y) 中具有最大元素 41。我们可以验证此 SMMH 的每个节点 y 都满足所述属性。
由于 SMMH 表示为一棵完全二叉树，因此它存储为一个隐式数据结构，实现了将完全二叉树映射到数组的标准方法。当 m = 1 时，最小和最大元素相同，并包含在 SMMH 根节点的左孩子中。
当 m > 1 时，最小元素位于根节点的左孩子中，最大元素位于根节点的右孩子中。因此，getMin 和 getMax 操作消耗 O(1) 时间。
很容易看出，具有空根节点和每个其他节点中包含一个元素的 m + 1 个节点的完全二叉树是 SMMH 当且仅当以下条件为真 -
A1 - 对于每个具有右兄弟的节点 y，y 中的元素小于或等于其右兄弟中的元素。
A2 - 对于每个具有祖父母节点的节点 y，祖父母节点的左孩子中的元素小于或等于 y 中的元素。
A3 - 对于每个具有祖父母节点的节点 y，祖父母节点的右孩子中的元素大于或等于 y 中的元素。
请注意，如果属性 A1 在节点 y 处满足，则在 y 处最多只有一个 A2 和 A3 可能被违反。通过实现属性 A1 到 A3，我们得到了用于插入和删除元素的简单算法。这些算法是对最小堆和最大堆的相应算法的简单改编。它们的复杂度为 O(log m)。
这里，我们指定插入操作。假设我们希望将 3 插入到图 1 的 SMMH 中。由于 SMMH 是一棵完全二叉树，因此我们必须在图 2 所示的位置向 SMMH 添加一个新节点；新节点标记为 B。
在我们的示例中，B 将表示一个空节点。现在 3 插入到节点 B 中。
1K+ 次查看
