ヒープ化されてない配列からヒープを作成する場合の計算量についてですが、1つのデータの挿入に O(log N) 要することから考えると、直感的には O(N log N) になりそうですが、実際には O(N) で可能です。

ref. なぜヒープ化 (heapify) は O(N) で可能なのか #競技プログラミング - Qiita