python 堆排序算法

OZABC最近在准备面试，正好复习到堆排序，正好总结一下

堆排序的算法思路基本如下：

1. 找到最后一个非叶子节点，进行第一次循环比较，找到第一个最值
2. 将找到的最值移动到末尾，长度-1，root=0，继续排序n-1次
3. 每次发生比较后需要在此循环比较，直到没有发生移动或者超过最大长度
4. 比较的时间复杂度O(lgn)，生成堆的时间复杂度为O(n)，所以总的时间复杂度为O(nlgn)
5. 堆排序是不稳定的排序

def build_heap(l):

    l_len = len(l)

    for i in range((l_len - 2) // 2, -1, -1):

        re_heap(l, l_len, i)

def build_heap_min(l):

    l_len = len(l)

    for i in range((l_len - 2) // 2, -1, -1):

        re_heap_min(l, l_len, i)

def re_heap(h, size, root):

    larger = root

    left = root * 2 + 1

    right = left + 1

    if left < size and h[left] > h[larger]:

        larger = left

    if right < size and h[right] > h[larger]:

        larger = right

    if larger != root:

        # need change

        h[larger], h[root] = h[root], h[larger]

        # continue

        re_heap(h, size, larger)

def re_heap_min(h, size, root):

    min = root

    left = root * 2 + 1

    right = left + 1

    if left < size and h[left] < h[min]:

        min = left

    if right < size and h[right] < h[min]:

        min = right

    if min != root:

        # need change

        h[min], h[root] = h[root], h[min]

        # continue

        re_heap_min(h, size, min)

def heap_sort(l):

    build_heap(l)

    l_len = len(l)

    for i in range(l_len - 1, -1, -1):

        l[0], l[i] = l[i], l[0]

        re_heap(l, i, 0)

    return l

def heap_sort_min(l):

    build_heap_min(l)

    l_len = len(l)

    for i in range(l_len - 1, -1, -1):

        l[0], l[i] = l[i], l[0]

        re_heap_min(l, i, 0)

    return l

if __name__ == '__main__':

    l = [4, 5, 6, 34, 67, 475, 545, 567, 3454]

    print heap_sort(l)

    print '-' * 36

    print heap_sort_min(l)