如何使用节点在堆数据结构中实现向下渗透功能？

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 何时为叶节点且没有子节点。

如何使用节点在堆数据结构中实现向下渗透功能？

how do I implement the percolate-down function in Heap data structure using nodes?

java

heap

data-structures