堆排序.md

算法流程

• 堆的定义

  堆包括最大堆和最小堆， 最大堆要求节点的元素都要不小于其孩子，最小堆要求节点元素都不大于其孩子，其中左右节点的顺序没有要求

• 建堆

  先将原数组建立成一颗完全二叉树，之后从下向上寻找第一个非叶子节点，从这一节点开始向上逐个检查调整每个节点

• 维护

  以最大堆为例，检查一个节点时，取其左右孩子中较大的一个与该节点比较，如果左右节点最大值大于该节点，则交换位置，并继续调整这一子树，否则这一节点的维护停止

• 输出结果 每次输出堆顶元素，并将堆中最后一个节点于堆顶交换，检查维护新的堆顶元素

代码

def sift_down(array, start, end):
    """
    调整成大顶堆，初始堆时，从下往上；交换堆顶与堆尾后，从上往下调整
    :param array: 列表的引用
    :param start: 父结点
    :param end: 结束的下标
    :return: 无
    """
    while True:

        # 当列表第一个是以下标0开始，结点下标为i,左孩子则为2*i+1,右孩子下标则为2*i+2;
        # 若下标以1开始，左孩子则为2*i,右孩子则为2*i+１
        child = 2*start + 1  # 左孩子的结点下标
        # 当结点的右孩子存在，且大于结点的左孩子时
        if child > end:
            break

        if child+1 <= end and array[child+1] > array[child]:
            child += 1
        if array[child] > array[start]:  # 当左右孩子的最大值大于父结点时，则交换
            array[child], array[start] = array[start], array[child],
            start = child  # 交换之后以交换子结点为根的堆可能不是大顶堆，需重新调整
        else:  # 若父结点大于左右孩子，则退出循环
            break

def heap_sort(array):  # 堆排序
    # 先初始化大顶堆
    first = len(array)//2 -1  # 最后一个有孩子的节点(//表示取整的意思)
    for i in range(first, -1, -1):  # 从最后一个有孩子的节点开始往上调整
        sift_down(array, i, len(array)-1)  # 初始化大顶堆

    print("初始化大顶堆结果:", array)
    # 交换堆顶与堆尾
    for head_end in range(len(array)-1, 0, -1):  # start stop step
        array[head_end], array[0] = array[0], array[head_end] # 交换堆顶与堆尾
        sift_down(array, 0, head_end-1)  # 堆长度减一(head_end-1)，再从上往下调整成大顶堆


if __name__ == "__main__":
    array = [16, 7, 3, 20, 17, 8]
    print(array)
    heap_sort(array)
    print("堆排序最终结果:", array)

应用

• 维护前k大元素
• python中有heapq模块实现了堆 实现操作有
  • heappush(heap, x)：向堆中添加元素
  • heappop(heap)：弹出堆中最小的元素，并且维持剩余元素的堆结构
  • heapify(heap)：将列表转换为堆
  • heapreplace(heap, x)：弹出堆中最小的元素，然后将新元素插入。
  • nlargest(n, iter)、nsmallest(n, iter)：用来寻找任何可迭代对象iter中的前n个最大的或前n个最小的元素。