在区间堆中插入元素

根据区间堆中存在的元素数量，可能会出现以下情况 -

• 奇数个元素：如果区间堆中的元素数量为奇数，那么新元素首先被插入到最后一个节点中。然后，新元素将与前一个节点的元素依次进行比较，并进行检查以满足区间堆的基本标准。如果新元素不满足任何标准，则它将从最后一个节点传输到根节点，直到满足所有条件为止。
• 偶数个元素：如果元素数量为偶数，则为插入新元素创建一个额外的节点。如果元素属于或位于父区间的左侧，它被视为在最小堆中；如果元素属于或位于父区间的右侧，它被视为在最大堆中。然后，它被逐一比较并从最后一个节点传递到根，直到满足区间堆的所有条件。如果元素位于或属于父节点本身的区间，则进程立即终止，并且不执行元素的传递。插入元素所花费的时间取决于满足所有条件所需的移动次数，即 O(log n)。

Arnab Chakraborty

更新于：02-Jan-2020

183 次浏览

开启你的 事业

通过完成课程获得认证

开始