algorithm - ヒープソート

ワーストケースでも O (n log (n)) なパフォーマンスが出せる。
* ベストもアベレージも O (n log (n))
ただし、平均速度はクイックソートの方が上。

def comp(a, b):
    if a > b:
        return 1
    elif a < b:
        return -1
    else:
        return 0

# 親と子を比較し、子の方が大きければ交換
# 交換があれば更なる交換がないか再帰的に調べる
def heapify(arr, comp_func, idx, max_idx):
    left = 2 * idx + 1
    right = 2 * idx + 2
    largest = 0
    if left < max_idx and comp_func(arr[left], arr[idx]) > 0:
        largest = left
    else:
        largest = idx
    if right < max_idx and comp_func(arr[right], arr[largest]) > 0:
        largest = right
    if largest != idx:
        tmp = arr[idx]
        arr[idx] = arr[largest]
        arr[largest] = tmp
        heapify(arr, comp_func, largest, max_idx)

# 子は必ず親より小さい、という性質を持つ 2 分木を作成する
# 大きい数字が勝ち上がっていく、トーナメントのようなイメージ
def buildHeap(arr, comp_func, n):
    for i in range(n / 2 - 1, -1, -1):
        heapify(arr, comp_func, i, n)
        
def heapSort(arr, n, comp_func):
    # 初回のみ下から木を作る
    buildHeap(arr, comp_func, n)
    for i in range(n - 1, 0, -1):
        # 最大値が配列先頭にあるので、終端と交換
        tmp = arr[0]
        arr[0] = arr[i]
        arr[i] = tmp
        # 一度木が作成済みなので先頭から交換の有無を調べる
        # 上位に交換がなければ、下位に影響はない
        heapify (arr, comp_func, 0, i)
        
a = range(0, 500)
random.shuffle(a)
print a
heapSort(a, len(a), comp)
print a