From what I see online, all seem to suggest that heapifying takes $\mathcal O (n)$ time, but it seems like it should always takes $\theta(n)$ time, even in the best case. Is something wrong with my pseudocode? Is there a more optimized way to do heapification?
Heapification(H[1...n])
for i <- floor(n/2) downto 1 do
k <-i; v <- H[k]
heap <- False
while !heap && 2k <= n do
j <- 2k
if j <= n
if H[j] < H[j+1]
j <- j+1
if H[j] > v
H[k] <- H[j]
k <- j
else heap <- true
H[k] <- v