0

您如何跟踪插入堆的位置：我认为使用检查每个子树高度的函数会将算法从 O(log N) 降级为 O(N)。

因此，您是在每个节点中保留一个变量，还是在具有最后一个插入点的堆中保留一个变量（如何定义？）。

4

1 回答 1

1

堆是“几乎满的”二叉树。所以你只有一个选择，你应该在哪里插入新元素，不需要高度检查——但是一个指向下一个元素应该插入的位置的指针。这当然足以确保 O(logn) 的高度

于 2011-03-13T11:20:51.443 回答