使用二叉树实现堆 [英] Implement Heap using a Binary Tree

问题描述

此问题之前已在Stack Exchange中提出，但未得到答复。

This question has been asked before in Stack Exchange but it went unanswered.

链接到之前提出的问题：
通过二叉树结构实现二进制堆

Link to the previously asked question: Binary Heap Implemented via a Binary Tree Structure

如何在二叉树中实现堆。要实现堆，了解最后一个填充节点和第一个未占用节点非常重要。这可以在树的级别排序中完成，但是时间复杂度将是O（n）以便找到第一个未占用的节点。那么，如何在O（logn）中的二叉树中实现堆？

How do I implement heap in a binary tree. To implement heap, it is important to know the last filled node and the first unoccupied node. This could be done in level ordering of the tree, but then the time complexity will be O(n) just to find the first unoccupied node. So, how to implement heap in a binary tree in O(logn)?

谢谢
Shekhar

Thanks Shekhar

推荐答案

要实现具有O（log n）时间复杂度的二叉树的堆，您需要将节点总数存储为实例变量。

To implement a heap with a binary tree with O(log n) time complexity, you need to store the total number of nodes as an instance variable.

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

Suppose we had a heap of 10 total nodes.

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

If we were to add a node...

我们将节点总数增加1。现在我们有11个节点。我们将新的节点总数（11）转换为其二进制表示形式：1011。

We increment the total number of nodes by one. Now we have 11 total nodes. We convert the new total number of nodes (11) to its binary representation: 1011.

使用总节点（1011）的二进制表示，我们摆脱了第一位数。然后，我们使用011在树中导航到下一个位置以插入节点.0表示向左移动，1表示向右移动。因此，对于011，我们将向左，向右，向右走......这将我们带到下一个要插入的位置。

With the binary representation of the total nodes (1011), we get rid of the first digit. Afterwards, we use 011 to navigate through the tree to the next location to insert a node in. 0 means to go left and 1 means to go right. Therefore, with 011, we would go left, go right, and go right...which brings us to the next location to insert in.

我们检查了一个节点等级，使时间复杂度为O（log n）

We examined one node per level, making the time complexity O(log n)

这篇关于使用二叉树实现堆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！