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)$
Managed to solve it.
There is an algorithm to build a heap in $\Theta (n)$ time called buildheap.