在堆中插入元素

在堆中插入元素包括两个步骤:

  1. 将元素插入堆的末尾。
  2. 重新排列堆中的元素。

在本文中,我将提供一种在堆末尾插入新元素的方法。 让我们考虑一种情况,已经存在具有元素9,11,5和3的最大堆。

现在,我们要在堆中插入7。 7将是堆中的第五个元素。 作为人类,我们只需要看一下图形就可以知道在哪里插入7,但是,计算机如何计算出来呢?

我将提供一种可以告诉计算机在哪里插入新元素的方法。

脚步:

  1. 计算堆中已经存在的元素数(否则,您可以跟踪它),然后向其加1。
  2. 将以上结果转换为二进制。
  3. 同时,按照以下4条规则从MSB (最高有效位)到LSB (最低有效位)和堆遍历上述二进制等效项。

规则1:第一位,即MSB将始终为1,永远不会为0(因为5的二进制数将为101而不是0101),并将指示根节点并开始从根节点遍历堆。

规则2:如果下一位为1,则遍历到右子节点。

规则3:如果下一位为0,则遍历到左子节点。

规则4:最后一位将指示可以添加新节点的位置。

例:

继续上面的示例。 我们要向包含9、11、5和3的堆中添加7。现在,7将成为要添加到堆中的第五个元素。 因此,根据规则1将指示根节点。

下一位是0,因此我们应该根据规则3遍历到左子节点。

下一位是1,它也是LSB,即最后一位,因此我们需要根据规则2遍历到正确的子节点,但根据规则4,最后一位将显示添加新节点的位置。 因此,新节点将添加到其父节点的右侧。

这样,我们就可以知道如何在堆中添加新节点。 之后,我们可以根据堆的类型重新排列元素。