堆排序思想：
1把堆看成列表，或者说把列表看成堆
2给我们一个无序的列表，把列表按堆排序，子节点小于父节点，这样我们有了一个堆
3把堆顶和堆的最后一个叶子结点的元素互换位置，然后通过向下调整让这个堆重新恢复所有的父节点大于子节点
4循环执行步骤3，相当于每次把堆顶最大的元素拿出来放到列表的最后位置，堆的节点则对应的渐趋1（同一个列表前面部分是堆，后面是排好序的列表，这样节省空间开销）
上面就是对排序的思想
因此在一个循环里面我们要确定i和j
再确定i和j的大小
依次循环，就能得到有序的列表
i 始终使我们要填补的位置，拿出tmp=2和子节点j上的9对比，谁大谁填补i的位置
j 是子节点的位置，如果右孩子节点大于左节点，则j指向右孩子节点
基础运算：
i-父节点
j-子节点
左孩子节点=i* 2-1
右孩子节点=i* 2-2
i-子节点 j-父节点=(i-1)//2
步骤：
堆的向下调整：
1定义变量i和j，i是空缺的节点的位置，j是它的子节点
i-父节点
j-子节点（父节点2-1得到左孩子节点，父节点2-2得到右孩子节点）
2循环向下调整（while），条件是子节点的index不超过high，即子节点不超过整个堆的的长度
3判断是否存在右孩子节点，右孩子节点是否大于左孩子，成立则将j指向右孩子
4判断子节点是否大于父节点，成立则交换位置，继续向下调整
5如果父节点大于子节点，表示堆合法，跳出循环，把tmp放在空位
def sift(rlist,low,high):
i=low#父节点
j=2*i+1#找到父节点的子节点（左孩子）
tmp=rlist[low]#保存父节点
#while循环里要做的事
# 1 逐级判断子节点是否大于父节点，大于则交换位置
# 2 子节点小于父节点，就把
while j<=high:#子节点不越界
if j+1<=high and rlist[j+1]>rlist[j]:#判断是否存在右孩子节点以及右孩子大于左孩子
j=j+1#把j指向右孩子
if rlist[j]>tmp:#如果子节点大于父节点
rlist[i]=rlist[j]#将子节点上移到父节点
i=j#子节点j就是下一个要判断的父节点
j=2*i+1#找到父节点的子节点（左孩子）
else:#如果父节点大于子节点，表示这个节点就是tmp的位置，就跳出循环，把tmp放在这个节点
break
rlist[i]=tmp #跳出循环把tmp放在这个节点,表示完成一次向下调整
建堆图解：
建堆代码：
def heapsort(li):
n=len(li)
for i in range((n-2)//2,-1,-1):
sift(li,i,n-1)
建堆可以复用sift函数，建堆就是让一个无序的堆有序，将堆分成若干个最小堆1,2,3,4，5，将其调整成有序堆
args：（n-2）//2 最后一个节点的父节点，-1 堆顶0(右不包，这里要传-1)，步长-1
i和j 控制了每次的调整都限定在1,2，3,4，5这样的最小堆
以上图为例，sift接收的i一次为5-4-3-2-1-，对应i上的元素以次为5-9-1-8-6
堆排序：
## 堆排序
for i in range(n-1,-1,-1):#i指向当前堆的最后一个位置，向上循环到0，这里倒叙循环是为了用i控制堆的大小，因为每循环一次堆的大小-1
li[0],li[i]=li[i],li[0]#把堆顶和堆最后一个位置交换，
sift(li,0,i-1)#开始向下调整，0是堆顶low，high是n-1，因为已经进行了一次堆顶和堆最后节点位置交换了，堆的长度向前移一位
完整代码：
def sift(rlist,low,high):
i=low#父节点
j=2*i+1#找到父节点的子节点（左孩子）
tmp=rlist[low]#保存父节点
# print(i,j)
#while循环里要做的事
# 1 逐级判断子节点是否大于父节点，大于则交换位置
# 2 子节点小于父节点，就把
while j<=high:#子节点不越界
if j+1<=high and rlist[j+1]>rlist[j]:#判断是否存在右孩子节点以及右孩子大于左孩子
j=j+1#把j指向右孩子
if rlist[j]>tmp:#如果子节点大于父节点
rlist[i]=rlist[j]#将子节点上移到父节点
i=j#子节点j就是下一个要判断的父节点
j=2*i+1#找到父节点的子节点（左孩子）
else:#如果父节点大于子节点，表示这个节点就是tmp的位置，就跳出循环，把tmp放在这个节点
break
rlist[i]=tmp #跳出循环把tmp放在这个节点,表示完成一次向下调整
def heapsort(li):
n=len(li)
##建堆
for i in range((n-2)//2,-1,-1):#从最后一个父节点开始，向上循环到0
sift(li,i,n-1)
## 堆排序
for i in range(n-1,-1,-1):#i指向当前堆的最后一个位置，向上循环到0，这里倒叙循环是为了用i控制堆的大小，因为每循环一次堆的大小-1
li[0],li[i]=li[i],li[0]#把堆顶和堆最后一个位置交换，
sift(li,0,i-1)#开始向下调整，0是堆顶low，high是n-1，因为已经进行了一次堆顶和堆最后节点位置交换了，堆的长度向前移一位
li=[i for i in range(100)]
print(li)
random.shuffle(li)
print(li)
heapsort(li)
print(li)
要排序的list：[0, 23, 32, 93, 19, 88, 64, 90, 50, 86, 36, 46, 75, 74, 2, 57, 47, 49, 3, 35, 4, 54, 83, 20, 65, 51, 34, 39, 72, 81, 26, 79, 28, 76, 9, 6, 21, 91, 92, 7, 69, 31, 22, 82, 53, 85, 25, 99, 61, 14, 29, 41, 67, 1, 27, 68, 42, 10, 77, 33, 71, 52, 38, 18, 62, 58, 15, 73, 30, 63, 60, 66, 56, 89, 44, 70, 97, 80, 16, 98, 87, 45, 17, 55, 78, 13, 40, 11, 84, 94, 24, 95, 48, 12, 5, 43, 8, 96, 59, 37] 建完堆的list：[99, 98, 96, 97, 95, 88, 81, 90, 93, 87, 94, 65, 75, 77, 71, 79, 76, 89, 92, 86, 78, 84, 85, 61, 37, 67, 34, 68, 74, 64, 52, 62, 58, 73, 63, 66, 49, 91, 80, 35, 69, 55, 40, 82, 54, 83, 25, 43, 59, 14, 29, 41, 51, 1, 27, 39, 42, 10, 72, 33, 2, 26, 38, 18, 57, 28, 15, 47, 30, 9, 60, 6, 56, 21, 44, 70, 3, 50, 16, 7, 19, 45, 17, 4, 31, 13, 22, 11, 23, 53, 24, 36, 48, 12, 5, 20, 8, 46, 32, 0] 堆排序：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]
