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.
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_heap
algorithm.
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!