2

给定一个中序遍历列表，创建二进制最小/最大堆的最佳方法是什么？

我试图限制以下结构：

  1. 二进制堆中没有要使用的数组。实现是基于节点的。 BinaryNode { value, parent, l_child, r_child }

  2. 让我们坚持使用 Max-Heap。

问题：我们能否比涉及 BubbleDown 的标准插入做得更好。

4

1 回答 1

3

有一个优雅的线性时间算法可以从一组值中构建一个最大堆，它比仅仅执行 n 个冒泡步骤要快。这个想法是建立一个由较小的最大堆组成的森林，然后将它们成对地连续合并在一起，直到所有元素都连接到一个最大堆中。使用精确的分析，可以证明该算法在 O(n) 时间内以非常好的常数因子运行。许多标准库都包含此功能；例如，C++ 有std::make_heap算法。

有关此算法的更多详细信息，包括算法草图、正确性证明和运行时分析，请查看之前的问题：https ://stackoverflow.com/a/6300047/501557

希望这可以帮助！

于 2011-12-26T18:23:19.783 回答