Constructing Min/Max Binary Heap

Question

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:

1. No array to be used in the binary-heap. Implementation is node-based. BinaryNode { value, parent, l_child, r_child }

2. Let's just stick to Max-Heap.

Question: Can we do better than standard insertion that involves BubbleDown.

Answer 1

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!