def sift(data, low, high):

    i = low      # 父节点

    j =  * i +    # 左子节点

    tmp = data[i]   # 父节点值

    while j <= high:    # 子节点在节点中

        if j < high and data[j] > data[j + ]:  # 有右子节点且右节点比父节点值大

            j +=

        if tmp > data[j]:

            data[i] = data[j]   # 将父节点替换成新的子节点的值

            i = j   # 变成新的父节点

            j =  * i +    # 新的子节点

        else:

            break

    data[i] = tmp   # 将替换的父节点值赋给最终的父节点

def heap_sort(data):

    n = len(data)

    # 创建堆

    for i in range(n//2-1, -1, -1):

        sift(data, i, n-)

    # 挨个出数

    for i in range(n-, -, -):    # 从大到小

        data[], data[i] = data[i], data[]     # 将最后一个值与父节点交互位置

        sift(data, , i-)

li = list(range())

random.shuffle(li)

print(li)

heap_sort(li)

print(li)

def random_list(n):

    '''

    生成随机数据

    :param n:

    :return:

    '''

    ret = []

    a1 = ['赵', '钱', '孙', '李', '邹', '吴', '郑', '王', '周']

    a2 = ['力', '好', '礼', '丽', '文', '建', '梅', '美', '高', '']

    a3 = ['强', '文', '斌', '阔', '文', '莹', '超', '云', '龙', '']

    ids = range(,  + n)

    for i in range(n):

        name = random.choice(a1) + random.choice(a2) + random.choice(a3)

        age = random.randint(, )

        dic = {'id': ids[i], 'name': name, 'age': age}

        ret.append(dic)

    return ret

def sift(data, low, high):

    i = low      # 父节点

    j =  * i +    # 左子节点

    tmp = data[i]   # 父节点值

    while j <= high:    # 子节点在节点中

        if j < high and data[j]['id'] < data[j + ]['id']:  # 有右子节点且右节点比父节点值大

            j +=

        if tmp['id'] < data[j]['id']:

            data[i] = data[j]   # 将父节点替换成新的子节点的值

            i = j   # 变成新的父节点

            j =  * i +    # 新的子节点

        else:

            break

    data[i] = tmp   # 将替换的父节点值赋给最终的父节点

def heap_sort(data):

    n = len(data)

    # 创建堆

    for i in range(n//2-1, -1, -1):

        sift(data, i, n-)

    # 挨个出数

    for i in range(n-, -, -):    # 从大到小

        data[], data[i] = data[i], data[]     # 将最后一个值与父节点交互位置

        sift(data, , i-)

li = random_list() # 生成数据

random.shuffle(li) # 将数据打乱

heap_sort(li)

print(li)