一、二叉堆的特性：
1、最大堆的堆顶是整个堆中的最大元素。
2、最小堆的堆顶是整个堆中的最小元素。
以最大堆为例，如果删除一个最大堆的堆顶（并不是完全删除，而是跟末尾的节点交换位置），经过自我调整，第2大的元素就会被交换上来，成为最大堆的新堆顶。
二、堆排序
1、把无序数组构建成二叉堆。
从小到大排序，则构建成最大堆;
从大到小排序，则构建成最小堆。
2、循环删除堆顶元素，替换到二叉堆的末尾，调整堆产生新的堆顶。
第1步，把无序数组构建成二叉堆，这一步的时间复杂度是O (n)。
第2步，需要进行n-1次循环。每次循环调用一次down_adjust方法，所以第2步的计算规模是(n-1) xlogn，时间复杂度为O ( nlogn) 。
两个步骤是并列关系，所以整体的时间复杂度是O (nlogn）。
如图所示：
def down_adjust(p_index,length,ll):'''下沉:param p_index: 父节点索引:param length: 大小:param ll: 数列:return:'''#保存父节点元素temp=ll[p_index]#左子节点索引sub_index=2*p_index+1#循环while sub_index <length:# 如果有右孩子，且右孩子的值大于左孩子的值，则定位到右孩子if sub_index+1<length and ll[sub_index+1]>ll[sub_index]:sub_index+=1# 如果父节点的值>=任何一个孩子的值,直接跳出if temp>=ll[sub_index]:break#无需真正交换#子节点元素赋给父节点元素ll[p_index]=ll[sub_index]#子节点索引重新赋值给父节点索引p_index=sub_index#子节点索引sub_index = 2 * sub_index + 1#父节点元素ll[p_index]=tempdef heapSort(ll):#1.把无序数组构成最大堆for i in range((len(ll)-2)//2,-1,-1):down_adjust(i,len(ll),ll)#2.循环删除堆顶元素，替换到二叉堆的末尾，调整堆产生新的堆顶。for i in range(len(ll)-1,0,-1):#最后一个与第一个元素交换t=ll[i]ll[i]=ll[0]ll[0]=t#下沉调整最大堆down_adjust(0,i,ll)if __name__ == '__main__':ll = [10, 8,9, 7, 5, 4, 6, 3,2]print('排序前：')print(ll)# 调用方法排序heapSort(ll)print('排序后：')print(ll)
相同点，堆排序和快速排序的平均时间复杂度都是O (nlogn)，并且都是不稳定排序。
不同点，快速排序的最坏时间复杂度是O (n2)，而堆排序的最坏时间复杂度稳定在O (nlogn)。
