java - 二叉最小堆的链表实现(操作遇到麻烦......)

Question

所以我正在尝试实现一个二进制最小堆。我了解二进制最小堆在结构和属性方面的含义。然而，当我尝试使用指针和节点实现它时，我遇到了困难。

我使用一个节点，它有右/左和指针、int元素和父指针。我还有一个 LastNode 指向最后插入的节点。

我的争吵是，当我插入一个元素时，我不知道该怎么做，就最后一个节点而言。这就是我的意思。

第 1 步。)假设堆为空，因此您创建一个 root，即 x，其中 x 包含该元素，并设置 root.left/right = null 和 LastNode = root.left。

  X
 / \
0   0

这是我陷入困境的部分。我知道当您创建另一个节点来存储另一个元素时，它将位于 X 的左侧或 LastNode 指向的位置。我的问题是我接下来要对 LastNode 做什么，我是否将其指向 x.right ？我试图让 insert(int x) 在 logN 中运行，并且 LastNode 操作在每个级别都会变得更长、更广泛。

有人能破解吗？谢谢

Answer 1

那么，您需要将元素插入堆的最后一层，然后从那里确定是否需要向上冒泡。因此，您需要 lastNode 指针来指示不是最后插入的元素(它很可能是最后插入的元素，但它可能已经一直向上成为根；这根本没有帮助)，而是指示的父元素您将在其中插入这个新元素。这有帮助吗？

(稍后编辑):有一种更优化的构建堆的方法，但我觉得这不是您现在需要的，所以这就是为什么我假设您将使用 is O(log n) 的简单插入对于每一个新元素。