一、堆排序简介
二、堆排序步骤
三、代码实现

一、堆排序简介

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆有最大堆和最小堆，在堆排序中： 最大堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排序。 最小堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排序。 堆排序的时间负责度为O(nlogn)

二、堆排序步骤

1、构建堆，本例以最大堆为例，生成升序序列。所以先构建最大堆。 2、删除堆顶元素，把它替换到二叉堆的末尾，调整产生的新的堆顶。 注意：这里并不是真的删除堆顶元素，只是让它和堆的最后一个元素进行交换，下次进行堆的调整时不再包括我们刚刚进行了数据交换的那个位置。

三、代码实现

def heapSort(arr=[]):
    build_heap(arr)
    for i in range(len(arr)-1,0,-1):
        arr[i],arr[0]=arr[0],arr[i]
        down_adjust(0,i,arr)
    return arr

def build_heap(arr):
    '''
    把无序数据构建为一个最大堆
    '''
    for i in range((len(arr)-2)//2,-1,-1):
        down_adjust(i,len(arr),arr)

def down_adjust(parent_index,length,arr=[]):
    temp=arr[parent_index]
    child_index=parent_index*2+1
    while child_index<length:
        if child_index+1<length and arr[child_index]<arr[child_index+1]:
            child_index += 1
        if temp>=arr[child_index]:
            break
        arr[parent_index]=arr[child_index]
        parent_index=child_index
        child_index=2*parent_index+1
    arr[parent_index]=temp

if __name__=='__main__':
    array = [3, 44, 38, 5, 15, 36, 46, 2, 48, 19]
    print(heapSort(array))