Question

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

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top