1
1
如果你想看
为什么?
你的
二进制堆必须保持Shape属性:它是一个完整的二叉树,但最下面的一行可能是左填充的。因此,如果知道堆中有多少节点,就可以很容易地找到下一个节点的插入点。考虑一下这个堆:
堆中有6个节点。每当堆中有6个节点时,树将如下所示,下一个节点的插入点将是最右节点的右子节点(本例中为3)。
有趣的是,节点号的二进制表示告诉我们该节点在哪里。例如,二进制中的6是
对于6,我们将从根向右转到节点3,然后向左转到节点6。
添加新节点时,请增加计数,然后按照上面的过程定位插入点。7是
当然,一旦将节点放置在树中以满足shape属性,就必须执行标准的重新heapify来调整树中的节点,以便维护heap属性。 |