二元堆 - 爲什麼remove函數需要調用bubbleUp方法？

Question

我已經通過eloquentjavascript網站學習JavaScript，來到一些代碼，我似乎無法理解：

remove: function(node) { 
    var length = this.content.length; 
    // To remove a value, we must search through the array to find 
    // it. 
    for (var i = 0; i < length; i++) { 
     if (this.content[i] != node) continue; 
     // When it is found, the process seen in 'pop' is repeated 
     // to fill up the hole. 
     var end = this.content.pop(); 
     // If the element we popped was the one we needed to remove, 
     // we're done. 
     if (i == length - 1) break; 
     // Otherwise, we replace the removed element with the popped 
     // one, and allow it to float up or sink down as appropriate. 
     this.content[i] = end; 
     this.bubbleUp(i); 
     this.sinkDown(i); 
     break; 
    } 
    }, 

我的問題是 - 爲什麼這個功能需要調用bubbleUp（）？ 如果end是二進制堆的最後一個值，並且通過push（）方法添加到堆中的每個值調用bubbleUp時，怎麼可能最終值的分數低於i的值？我對數據結構很陌生，似乎無法弄清楚這一點。

Answer 1

想象一下，一個最小堆像這樣：

 1 
    10  2 
18 20 3 4 

現在，假設你刪除20。你的代碼基本上就是代替4。

 1 
    10  2 
18 4 3 

因爲4 < 10，它必須冒泡以滿足最小堆的要求。