最大ヒープを作り、根の最大値を末尾へ移した後、残りの範囲でヒープ条件を復元します。親子の位置は配列内で計算できるため、別の木は保存しません。

配列と木を同期して表示するヒープソートシミュレーター

再生・ステップ実行・スライダーで操作できます。下の木は、棒グラフと同じ配列の別の見方です。

最良O(n log n)

平均O(n log n)

最悪O(n log n)

追加領域O(1)

安定いいえ

ヒープ構築O(n)

配列そのものが木になる

位置iの子は2i+1と2i+2、親は(i−1)//2です。sift_downは大きい方の子と交換し、ヒープ条件を満たすまで下がります。1回の移動はO(log n)段なので、繰り返し取り出すとO(n log n)になります。

初期構築では最後の親から根へ向かってsift_downします。大半のノードは下層にあり移動距離が短いため、構築全体はO(n)です。

演習：優先度付きキューとしてのヒープ

ヒープソートを自作するより、優先度付きキューを使う場面が一般的です。Pythonの heapqは最小ヒープです。数値の符号を反転すると最大ヒープとして使えます。大きい方からk個を求めるには、サイズkの最小ヒープでO(n log k)にできます。

import heapq
h = []
for x in a:
    heapq.heappush(h, x)
    if len(h) > k:
        heapq.heappop(h)    # ヒープの最小値を除く
# hには大きい方からk個が残る