ノードを使用したヒープデータ構造でpercolate-down関数を実装するにはどうすればよいですか？

Question

私は、ノードでバイナリツリーを作成し、配列ではなく、最大ヒープデータ構造を作成しています。 今、percolate-down関数を作成したいと思いますが、この関数をどのように実装する必要がありますか？それ以外の方法はありませんが、仕事をするための再帰はありますか？私はループを使用しようとしていますが、私の試行はすべて失敗しました。誰かが私を助けてくれることを願っています。

Answer 1

私はこのような何かが動作するはずだと思う：

do { 
    var currNode = root 
    var maxChild = if (currNode.left.value > currNode.right.value) currNode.left else currNode.right 

    if (currNode.value < maxChild.value) { 
     val tempValue = currNode.value 
     currNode.value = maxChild.value 
     maxChild.value = tempValue 

     currNode = maxChild 
    } else { 
     break 
    } 
} while (true) 

再帰はループ（またはその逆）を考えるの唯一の別の方法です。 再帰的な形で同じ溶液：

def percolateDown(currNode: Node): Unit = { 
    val maxChild = if (currNode.left.value > currNode.right.value) currNode.left else currNode.right 

    if (currNode.value < maxChild.value) { 
     val tempValue = currNode.value 
     currNode.value = maxChild.value 
     maxChild.value = tempValue 

     percolateDown(maxChild) 
    } 
} 

percolateDown(root) 

編集：いくつかのより多くのチェックがcurrNodeが葉で、子供を持っていないときを検出するために必要とされます。