java - 使用二叉树实现堆

Question

这个问题以前在 Stack Exchange 中被问过，但没有得到回答。

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

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

谢谢谢卡尔

Answer 1

要用时间复杂度为 O(log n) 的二叉树实现堆，需要将节点总数存储为实例变量。

假设我们有一个总共有 10 个节点的堆。

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

我们将节点总数递增 1。现在我们总共有 11 个节点。我们将新的节点总数 (11) 转换为其二进制表示形式:1011。

有了总节点数 (1011) 的二进制表示，我们去掉了第一个数字。之后，我们使用 011 在树中导航到下一个位置以插入节点。0 表示向左走，1 表示向右走。因此，对于 011，我们将向左、向右、向右……这将我们带到下一个要插入的位置。

我们每层检查一个节点，使得时间复杂度为 O(log n)