从最大堆中提取根

Question

我正在努力编写一个递归算法来从最大堆中提取max（root）。堆被构造为树。我知道我应该用根交换最后一个节点，然后递归下推。但是，互联网上没有伪代码或堆栈溢出来处理树。我见过的提取算法是基于数组的。

因此，我找到了最合适的叶子。

您有什么建议的解决方案吗？

---

void find_last(heap_node* root,int level,int* last_level,bool isRight,heap_node** res){

if(root ==  NULL)
    return;

if(isRight && !root->left && !root->right && level > *last_level){
    *res = root;
    *last_level = level;
    return;

}
find_last(root->right,level+1,last_level,true,res);
find_last(root->left,level+1,last_level,false,res);
}

并且我进行了这样的函数调用

            heap_node* last = NULL;
            int last_level = -1;
            find_last(root,0,&last_level,false,&last);

这是找到最深的右节点的代码。而且它不起作用：D

Answer 1

要有效地找到实现为树的堆中的最后一个节点，需要维护节点数。也就是说，您知道堆中有多少个项目。

如果您知道堆中有多少个项目，那么您将获得该数字的二进制表示形式，并使用它来遍历树到最后一个节点。让我给你举个例子。你有这个堆：

         1
     /       \
    2         3
  /   \     /   \
 4     5   6

堆中有6个项目。二进制表示为110。

现在，在二进制表示形式中从右向左移动。您删除第一个“ 1”，并且您位于根节点。规则是，如果数字为“ 1”，则向右移动；如果数字为“ 0”，则向左移动。在根节点上，您有10。因此，您右移并删除该数字，剩下0。您在标记为“ 3”的节点上。剩余的数字是0，因此您向左走。这会将您置于堆中的最后一个节点。

筛选堆的算法是相同的，而不管堆是表示为数组还是树。当然，交换节点所采取的实际步骤是不同的。交换节点时，必须注意正确设置子指针。人们经常忘记的一个地方是将根节点与最后一个节点交换时。

我的建议是先编写代码，然后在调试器中单步执行，以确保您正确分配了指针。