构建最小/最大二叉堆
给定一个中序遍历列表，创建最小/最大二进制堆的最佳方法是什么？
我试图限制以下构造：
二进制堆中没有要使用的数组。实现是基于节点的。
BinaryNode { value,parent, l_child, r_child }让我们坚持使用 Max-Heap。
问题：我们能否做得比涉及 BubbleDown 的标准插入更好。
Given an inorder-traversal list, what's the best way to create a Binary Min/Max Heap?
I'm trying to confine with the following constructs:
No array to be used in the binary-heap. Implementation is node-based.
BinaryNode { value, parent, l_child, r_child }Let's just stick to Max-Heap.
Question: Can we do better than standard insertion that involves BubbleDown.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
有一种优雅的线性时间算法可以从一组值构建最大堆，该算法比仅执行 n 个冒泡步骤渐近更快。这个想法是建立一个较小的最大堆森林，然后不断地将它们成对合并在一起，直到所有元素都加入到一个最大堆中。通过精确分析，可以看出该算法运行时间为 O(n)，并且具有非常好的常数因子。许多标准库都包含此函数；例如，C++ 有
std::make_heap算法。有关该算法的更多详细信息，包括算法草图、正确性证明和运行时分析，请查看之前的问题：https ://stackoverflow.com/a/6300047/501557
希望这有帮助！
There is an elegant linear-time algorithm for building a max-heap from a collection of values that is asymptotically faster than just doing n bubble steps. The idea is to build a forest of smaller max-heaps, then continuously merge them together pairwise until all the elements are joined into a single max-heap. Using a precise analysis, it can be shown that this algorithm runs in O(n) time with a very good constant factor. Many standard libraries include this function; for example, C++ has the
std::make_heapalgorithm.For more details about this algorithm, including a sketch of the algorithm, a correctness proof, and a runtime analysis, check out this earlier question: https://stackoverflow.com/a/6300047/501557
Hope this helps!