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:

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.

Are you assuming that the heap is a complete binary tree? Or is this any tree that obeys the heap property? — templatetypedef, Dec 26 '11 at 09:20

score 3 · Accepted Answer · edited May 23 '17 at 12:30

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!

Constructing Min/Max Binary Heap

1 Answers1