Any form of binary search tree can be converted into a complete binary tree in $\Theta(n)$ time.
And heapification of a complete binary tree into a max or a min heap can be done in $\Theta(n)$ time.
Overall , time would be $\Theta(n)$+$\Theta(n)$ = $\Theta(n)$