2
$\begingroup$

Max-heap is called a "strong" max-heap if all the nodes at certain level are less than all the nodes at the level before them. What is the most efficient way to build such a heap from a given array?

I was thinking about something similar to the regular build heap algorithm: scanning the array from right to left, compare every node to all of the nodes at the level below her, replace her with the max node and continuing until it reaches to the right position. However, I'm not sure How to make it more efficient. Thanks

$\endgroup$
2
$\begingroup$

Here's a simple way to approach it. Let's assume the array has $n = 2^k - 1$ distinct elements for convenience.

  1. Find the median in $O(n)$ using quickselect.

  2. Partition into two halves (greater and lesser-equal).

  3. Insert the lesser-equal half all as leaf nodes (deepest empty nodes).

  4. Repeat 1-3 on the greater half until you only have 1 value left which will be the max value.

Time complexity is: $$T(n) = T\left(\frac{n}{2}\right) + \Theta(n)$$ Which overall is linear $O(n)$ time complexity.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.