一、二叉堆的特性：
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]=temp
def 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)。