从最大堆中提取根

Question

我正在努力编写一个递归算法以从最大堆中提取最大（根）。堆被构造为树。我知道我应该将最后一个节点与根节点交换并递归地将其向下推。但是网上并没有伪代码或者stack overflow来处理树。我见过的提取算法都是基于数组的

假设我找到了最右边的叶子。

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

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，所以你往左走。这使您位于堆中的最后一个节点。

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

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

从最大堆中提取根

Extract the root from a max heap

heap

max-heap