# 要素数Nの配列Aでヒープを構築する
buildHeap(A):
    for i ← N/2 - 1 downto 0:
        downHeap(A, i)

# 要素数Nの配列Aで表されたヒープのノードiからダウンヒープを行う
# 挿入ベースの実装
downHeap(A, i): 
    largest       # 最大の値を持つノード
    cur ← i; # 現在地
    val ← A[i]   # 起点の値を一時的に退避

    while True:
        # 最大値を持つノードを探す
        if left(cur) < N and right(cur) < N:  
            # 左右に子を持つ場合
            if A[left(cur)] > A[right(cur)]:
                largest ← left(cur)
            else:
                largest ← right(cur)
        else if left(cur) < N:                  
            largest ← left(cur)   # 左の子のみを持つ場合
        else if right(cur) < N:
            largest ← right(cur)  # 右の子のみを持つ場合
        else:
            largest ← NIL

        if largest = NIL: break         # cur が葉の場合は終了
        if A[largest] ≤ val: break  # 起点の値以下の場合は終了
      
        A[cur] ← A[largest]
        cur ← largest      # 大きい方に向かって降下

    A[cur] ← val # 起点の値を挿入位置に戻す