def sift(nums, low, high):
    # 构造大根堆（假设左右子树已是大根堆）。
    # 索引由0开始。

    # 递归版本，空间复杂度不为O(1)
    # left, right = 2*low+1, 2*low+2
    # large_index = low
    # if left<=high and nums[low]<nums[left]:
    #     large_index = left
    # if right<=high and nums[left]<nums[right]:
    #     large_index = right
    # if large_index != low:
    #     nums[low], nums[large_index] = nums[large_index], nums[low]
    #     sift(nums, large_index, high)

    # 非递归版本，空间复杂度O(1)
    i, j = low, low*2+1     # R[j]是R[i]的左孩子
    tmp = nums[i]   # tmp保存根节点的值
    while j <= high:
        if j < high and nums[j] < nums[j+1]:
            j += 1
        if tmp < nums[j]:
            nums[i] = nums[j]
            i = j
            j = 2*i+1
        else:
            break
    nums[i] = tmp


def HeapSort(nums):
    low, high = 0, len(nums)-1
    i = len(nums)//2-1  # 最大非叶节点索引（索引由0开始）
    while i >= 0:
        sift(nums, i, high)
        i -= 1
    for i in range(high, 0, -1):
        nums[0], nums[i] = nums[i], nums[0]
        sift(nums, 0, i-1)
    return nums


inputs = [1, 2, 34, 35, 23, 56, 2, 13]
print(HeapSort(inputs))    # [1, 2, 2, 13, 23, 34, 35, 56]