【每日一题的算法】2020.09.10堆排序

参考：https://www.jianshu.com/p/d174f1862601

堆排序涉及到的概念

• 堆排序是利用 堆进行排序的
• 堆是一种完全二叉树
• 堆有两种类型: 大根堆 小根堆

• 两种类型的概念如下：
  大根堆：每个结点的值都大于或等于左右孩子结点
  小根堆：每个结点的值都小于或等于左右孩子结点
  因为比较抽象，所以专门花了两个图表示

主要理解怎么生成大顶堆！其余还是很好理解的。当然这个写大顶堆的方式不一定是最合适的方式。

你能写出伪代码吗？如果能也算自己理解了

讲解：

• 因为引入了一个辅助空间，所以使L_length = len(L) - 1
• 第一个循环做的事情是把序列调整为一个大根堆(heap_adjust函数)
• 第二个循环是把堆顶元素和堆末尾的元素交换(swap_param函数)，然后把剩下的元素调整为一个大根堆(heap_adjust函数)

import timeit
from collections import deque


# 将最大值调到最后
def swap_param(iList,i,j):
    iList[i], iList[j] = iList[j], iList[i]
    return iList

# 调整二叉树
def heap_adjust(iList, start, end):
    # 开始的序列号
    temp = iList[start]

    i = start
    j = 2 * i

    while j <= end:
        if(j < end) and (iList[j] < iList[j+1]):
            j += 1
        if temp < iList[j]:
            iList[i] = iList[j]
            i = j
            j = 2 * i
        else:
            break

    iList[i] = temp

# 按推排序
def heapSort(L):
    L_length = len(L) - 1


    # 构造一个堆，将堆中所有数据重新排序
    first_sort_count = int(L_length / 2)
    for i in range(first_sort_count):
        heap_adjust(L, first_sort_count - i, L_length)

    # 按对排序
    for i in range(L_length - 1):
        L = swap_param(L, 1, L_length - i)  # 将最大值调到最后
        heap_adjust(L, 1, L_length - i - 1) # size递减，保证最大值不会被重新排序

    return [L[i] for i in range(1, len(L))]


if __name__ == "__main__":
    L = deque([50, 16, 30, 10, 60, 90, 2, 80, 70])
    L.appendleft(0)  # 左边插入一个数0 ，因为二叉数是从1开始的。
    L = list(L)  # 转成列表才能进行列表的操作
    print(heapSort(L))
    print(timeit.timeit("heapSort(iList)", "from __main__ import heapSort,iList", number=100))

结果：
[2, 10, 16, 30, 50, 60, 70, 80, 90]
0.0007214