给 Depa 插入元素
如需给 deap 数据结构插入元素,我们可能需要以下过程来计算最小值和最大值:
过程 min_vale(m)://计算 deap 中的最小值。返回 m-2log2(m-1);
过程 max_vale(m)://计算 deap 中的最大值。返回 m+2log2(m-1);
deap 数据结构的插入操作可以按以下方式完成:
- 对于任何堆 b[ ],我们都应该检查 m 是否为 deap 中的最大堆中的一个位置。
- 然后,我们将计算 deap 中的最小值和最大值。
- 现在,比较左子树和右子树中的键值。
- 最后,我们按照以下算法执行插入操作。
Procedure deap_insertion(b[], y, m): if (m==1) b[2]=y; else{ if(m is in maximum subtree){ index=min_value(m); if(y<b[index]){ b[m]=b[index]; insert y in minimum subtree; } else insert y in maximum subtree; } else { index=max_value(m); if(x>b[index]){ b[m]=b[index]; insert y into maximum subtree; } else insert y into minimum subtree; }
广告