堆排序

 堆排序是指利用堆积树（堆）这种数据结构设计的排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引元素。堆分为大根堆和小根堆，是完全二叉树；大根堆的要求是每个节点的值都不大于其父节点的值，A[PARENT[i]]>=A[i]。再数组的非降序排序中，需要使用的是大根堆。跟进大根堆的要求可知，最大的值一定再堆顶。

# -*- coding: utf-8 -*-
"""
下标： 0,1,2,3,4
列表：[2,5,1,9,0]
2*i+1<size
i<(size-1)//2
"""
# 1、构建堆
def maxHeapify(heap, heapSize, root):  # 再堆中，做结构调整使得父节点的值大于子节点的值
    left = 2 * root + 1
    right = left + 1
    larger = root
    if left < heapSize and heap[larger] < heap[left]:
        larger = left
    if right < heapSize and heap[larger] < heap[right]:
        larger = right
    if larger != root:  # 如果做了堆调整则larger的值等于左节点或者右节点的，这个时候对调值操作
        heap[larger], heap[root] = heap[root], heap[larger]
        maxHeapify(heap, heapSize, larger)

# 2、构建排序
def heapSort(heap):
    # 构建大顶堆
    heapSize = len(heap)  # 堆的长度
    for i in range((heapSize-1) // 2, -1, -1):  # 从后往前出数，从下至上的构建大顶堆
        maxHeapify(heap, heapSize, i)
    # 将根节点与最后一个元素交换位置，重新调整为大顶堆，分别与后续位置交换
    for i in range(len(heap) - 1, -1, -1):
        heap[0], heap[i] = heap[i], heap[0]
        # 构建局部大顶堆
        maxHeapify(heap, i, 0)
    return heap


if __name__ == '__main__':

    import numpy as np
    li=np.arange(10)
    print(li)
    heapSort(li)
    print(li)