构建最小/最大二元堆

Question

鉴于中序遍历列表，什么是创建一个二进制最小值/最大值堆的最佳方式？

我想用下面的结构来限制：

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

2. 让我们来坚持Max-Heap。

问：我们可以做的比这涉及BubbleDown标准插好。

Answer 1

没有为从值的集合，是渐近比只是做Ñ气泡步骤更快构建最大堆优雅线性时间算法。这个想法是建立较小的MAX-堆森林，然后连续直到所有元素都被加入到一个单一的最大堆它们合并在一起配对。使用精确的分析，可以证明，该算法在O（n）的时间运行具有非常好的常数因子。许多标准库包含此功能;例如，C++有std::make_heap算法。

有关此算法的详细信息，包括算法的草图，正确性证明和运行时分析，看看这个早些时候问题：https://stackoverflow.com/a/6300047/501557

希望这有助于！