ヒープソート

C言語のアルゴリズム本を見ながら、Pythonにて書き換えてみる。
ヒープソートはこんな感じ。

def downheap(buff, parent, bottom):
    tmp = buff[parent]

    while True:
        cl = parent * 2 + 1
        cr = cl + 1

        if cl >= bottom:
            break
        if cr < bottom and buff[cl] < buff[cr]:
            cl += 1
        if tmp > buff[cl]:
            break

        buff[parent] = buff[cl]
        parent = cl
    buff[parent] = tmp


def heapsort(buff):
    size = len(buff)
    for i in range(size / 2 - 1, -1, -1):
        downheap(buff, i, size)

    for j in range(size - 1, 0, -1):
        tmp = buff[j]
        buff[j] = buff[0]
        buff[0] = tmp

        downheap(buff, 0, j)

if __name__ == '__main__':
    data = [2, 4, 6, 8, 10, 1, 3, 5, 7, 9]
    heapsort(data)
    print data

書き換えながら、ループを抜ける判定条件に悩む。どうして'A >= B'になるのか理解できなかったけれど（AとBがイコールになることはあるの？）、デバッガの助けを借りて解決。デバッガ便利ですね。

$ pdb heap.py 
> /tmp/heap.py(4)()
-> def downheap(buff, parent, bottom):
(Pdb) b 12, cl == bottom
Breakpoint 1 at /tmp/heap.py:12
(Pdb) r
> /tmp/heap.py(12)downheap()
-> break
(Pdb) p parent, cl, bottom
(3, 7, 7)
(Pdb) c
> /tmp/heap.py(12)downheap()
-> break
(Pdb) p parent, cl, bottom
(0, 1, 1)