# 堆排序(没用递归)
#第一步:调整三个节点:父节点和左右子节点,使其成为大根堆,如果while能一直向下循环,那么这次操作就是一次向下循环
def sift(li, low, high):
    """
    :param li: 列表
    :param low: 堆的根节点位置
    :param high: 堆的最后一个元素的位置,high是最后一个数字的索引,超了high就不存在了
    :return:
    """
    i = low # i最开始指向根节点,根节点数字的索引
    j = 2 * i + 1 # j开始是左孩子,j是i的左孩子的索引
    tmp = li[low] # 把堆顶存起来
    while j <= high: # 只要j位置有数
        #如果右孩子节点存在,就和左孩子节点比较大小,把大的值放到l[j]中
        if j + 1 <= high and li[j+1] > li[j]: # 如果右孩子有并且右孩子比左孩子大,j + 1 <= high保证右孩子不超索引范围
            j = j + 1  # j指向右孩子
        #如果子节点中最大值大于父节点的值,那就将父节点的值改成最大的子节点的值,此时i指的是父节点的索引,l[j]是三个节点中的最大值
        if li[j] > tmp: #子节点找到了最大的li[j],他要和根节点(如果不在顶层就是父节点了)的数字比大小,大的放在根节点
            li[i] = li[j]
            i = j           # 往下看一层,相当于i+=1,i向下走了一层,j也就向下走一层,找到了下一层的左孩子
            j = 2 * i + 1
        #如果前面两个if都不成立,那么父节点(tmp)的值就是三个节点中最大的了
        else:       # tmp更大，把tmp放到i的位置上
            li[i] = tmp     # 把tmp放到某一级领导位置上
            break
    #如果j超过了索引范围,那么此时i就指到了叶子节点(也就是最后一行了),那么就证明tmp是最小的,就把tmp放到最后一行空着的的叶子节点(li[i])即可
    else:#此时j>high,而i到了最后一行了,就把tmp放到最后一行的子叶了
        li[i] = tmp  # 把tmp放到叶子节点上


#建堆+出列表
def heap_sort(li):
    n = len(li)
    # 循环所有父节点建堆(重点:倒序循环父节点,从最下面的父节点开始循环)
    for i in range((n-2)//2, -1, -1):
        #先从最后一个节点的父节点开始循环,
        # 最后一个节点假设是i,它的父节点就是(i-1)//2这是固定的算法，不管是左子节点还是右子节点,
        # 现在最后一个数字索引是n-1,那么他的父节点就是（n-2）//2
        # i表示建堆的时候调整的部分的根的下标,每次i都是一个父节点,调整的是他的子树(只包含自己的两个子节点)
        #这里是从(n-2)//2遍历到0(顾头不顾尾),倒序(-1)
        sift(li, i, n-1)
        #这里n-1一直指代这个堆的最后一个叶子节点,
        # 其实他应该变化,每次都应该指该子树的右子节点,
        # 但是这个不容易求,n-1肯定比其他子树的右子节点大,用它限制肯定会多算几步,但是一定不会错

    # 建堆完成了(是按照堆的顺序排的数字)
    print('跟堆建成:',li)#现在出来的列表是按照堆的顺序拿出来的,还要最后排一下序

    #按照列表的顺序排序()
    for i in range(n-1, -1, -1):
        # i 每次取值都是指向当前堆的最后一个元素
        #从n-1遍历到0,每次步长是-1,就相当于是列表从最右端每次都向最左端挪一位
        li[0], li[i] = li[i], li[0]
        sift(li, 0, i - 1)
        #i-1是新的high,i指的是最后一个数字,他现在放的是根节点那个最大数字,
        # 循环一次就相当于最大值找到了,再循环一次就又找了个第二大的


li = [i for i in range(100)]
import random
random.shuffle(li)
print('手动建的乱序表:',li)

heap_sort(li)
print('排序后的结果:',li)