1
$\begingroup$

We are given a binary max (every node is larger than its children) heap with $n$ elements.

We now change $\frac{n}{4}$ of the elements at random. We don't know which ones and to which value. And so, it is now a possibility that the heap is no longer a valid max heap.

Show that the minimum number of steps required to fix this into a max heap is $\Theta (n)$.

I realize why this can't be lower than $n$. after all, we need to access every element in the heap to check if it was changed or not, it can't be less then $n$, but why is the fastest way $n$? I can't think of such an algorithm.

The algorithm i came up with, which is perhaps the naive one, is to insert all of the values of the heap to an array, and sorting it. but that is $\Theta (n \log n)$

$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

Managed to solve it.

There is an algorithm to build a heap in $\Theta (n)$ time called buildheap.

$\endgroup$
2
  • 1
    $\begingroup$ Could you add a link to that algorithm here, so that other users having the same problem can have an answer? Thank you. $\endgroup$
    – Hippalectryon
    Commented Oct 4, 2014 at 11:24
  • $\begingroup$ The algorithm is recursive: Starting from the root, buildheap(leftchild), then buildheap(rightchild), then heapify the root. By master's theorem that runs in O(n) $\endgroup$
    – Oria Gruber
    Commented Oct 18, 2014 at 13:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .