correcting an invalid binary heap in $\Theta (n)$ 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.