二分ヒープ（二分ヒープ配列表現）における build-heap（配列からヒープを構築する操作）の計算量はどれか？

配列からヒープを構築する際の一般的なアルゴリズム（下から非葉ノードに対して heapify を行う方法）は各レベルでの操作回数とノード数の関係により総コストが O(n) になります。個々の heapify は最悪 O(log n) ですが、多くのノードは浅い位置にあり合計で線形時間に抑えられます。要素を1つずつ insert する方式だと O(n log n) になる点と対照的です。