最小-最大堆

最小-最大堆被定义为包含交替的最小（偶数）和最大（奇数）层次的完全二叉树。偶数层次表示为例如 0、2、4 等，奇数层次表示为 1、3、5 等。

我们将在下一部分中认为根元素位于第一层，即 0。

最小-最大堆示例

最小-最大堆的特征

  • 最小-最大堆中的每个节点都与数据成员（通常称为键）相关联，其值用于计算节点在最小-最大堆中的顺序。
  • 根元素是最小-最大堆中的最小元素。
  • 作为最大（奇数）层次的第二层中的两个元素之一的最大元素是最小-最大堆中的最大元素
  • 假设 y 是最小-最大堆中的任意节点。
  • 如果 y 位于最小（偶数）层次，则 y.key 是具有根节点 y 的子树中所有键中最小的键。
  • 如果 y 位于最大（奇数）层次，则 y.key 是具有根节点 y 的子树中所有键中最大的键。
  • 最小（最大）层次上的节点表示为最小（最大）节点。

最大-最小堆定义为最小-最大堆的反义词；在这样的堆中，最高值存储在根节点中，而最小值存储在根节点的一个子节点中。

更新于：2020 年 01 月 03 日

6 千多次浏览

开启你的 职业生涯

通过完成课程获得认证

开始
广告