关系数据结构

全元素对应和叶元素对应是更为复杂的关系技术。这两种技术中，一半元素位于最小优先级队列，另一半元素位于最大优先级队列。如果元素数量为奇数，则一个元素存储在缓冲区中。该缓冲元素既不属于最小优先级队列，也不属于最大优先级队列。在全元素对应技术中，最小优先级队列中的每个元素 x 都与最大优先级队列中的一个不同元素 y 配对。(x, y) 是元素的一对对应元组，其中 priority(x) <= priority(y)。

图 E 显示了 11 个元素 3、4、5、5、6、6、7、8、9、10、11 的全元素对应堆。元素 10 位于缓冲区。对应元组由红色箭头表示。

图 E：全元素对应堆

在叶元素对应技术中，最小优先级队列和最大优先级队列的每个叶元素都需要成为一对对应元组的一部分。非叶元素不需要属于任何对应元组。图 F 显示了叶元素对应堆。

图 F：叶元素对应堆

全元素对应和叶元素对应结构所需的空间比对偶结构少。但是，全元素对应和叶元素对应结构的 DEPQ 算法比对偶结构更为复杂。在三种对应技术中，叶元素对应是最快的 DEPQ 对应结构。

Arnab Chakraborty

更新于：2020 年 1 月 3 日

已浏览 322 次

开启您的 职业

完成课程即可获得认证

开始