在區間堆中插入元素

根據區間堆中存在的元素數量，可能會出現以下情況 -

• 奇數個元素：如果區間堆中的元素數量為奇數，那麼新元素首先被插入到最後一個節點中。然後，新元素將與前一個節點的元素依次進行比較，並進行檢查以滿足區間堆的基本標準。如果新元素不滿足任何標準，則它將從最後一個節點傳輸到根節點，直到滿足所有條件為止。
• 偶數個元素：如果元素數量為偶數，則為插入新元素建立一個額外的節點。如果元素屬於或位於父區間的左側，它被視為在最小堆中；如果元素屬於或位於父區間的右側，它被視為在最大堆中。然後，它被逐一比較並從最後一個節點傳遞到根，直到滿足區間堆的所有條件。如果元素位於或屬於父節點本身的區間，則程序立即終止，並且不執行元素的傳遞。插入元素所花費的時間取決於滿足所有條件所需的移動次數，即 O(log n)。

Arnab Chakraborty

更新於：02-Jan-2020

183 次瀏覽

開啟你的 事業

透過完成課程獲得認證

開始