java – 使用二叉树实现堆

发布时间：2020-12-14 16:32:38 所属栏目：Java 来源：网络整理

导读：Stack Exchange中已经提出了这个问题,但没有得到答复. 链接到先前提出的问题： Binary Heap Implemented via a Binary Tree Structure 如何在二叉树中实现堆.要实现堆,了解最后一个填充节点和第一个未占用节点很重要.这可以在树的级别排序中完成,但是时间复

Stack Exchange中已经提出了这个问题,但没有得到答复.

链接到先前提出的问题：
Binary Heap Implemented via a Binary Tree Structure

如何在二叉树中实现堆.要实现堆,了解最后一个填充节点和第一个未占用节点很重要.这可以在树的级别排序中完成,但是时间复杂度将是O(n),只是为了找到第一个未占用的节点.那么,如何在O(logn)中的二叉树中实现堆？

谢谢
谢卡尔

解决方法

要实现具有O(log n)时间复杂度的二叉树的堆,需要将总数作为实例变量存储.

假设我们有一堆10个总节点.

如果我们要添加一个节点…

我们将节点总数递增1.现在我们有11个总节点.我们将新的总数(11)转换为二进制表示：1011.

使用总节点(1011)的二进制表示,我们摆脱第一个数字.之后,我们用011来浏览树到下一个插入节点的位置,0表示向左移,1表示右移.因此,在011的时候,我们会去左边,右边,这样我们就可以进入下一个位置.

我们检查每个级别的一个节点,使得时间复杂度O(log n)

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!