Heapify

Heapify is the process of creating a heap data structure from a binary tree.

We can create a heap from an array in $\Theta (n)$, and not $\Theta (n\log n)$. The reason is that we are starting from the last value of the heap in the array.

• Starts from the parent of the last element in the array and iteratively performs the fix-down operation to maintain heap property. fix-down is constant time $O(1)$ therefore he overall time is $\Theta (n)$.

Answer from quiz Module 2:

last = floor((n - 2) / 2)
for i from last to 0:
	fix-down(A[i])
end for

Used in Heap Sort.