改进参考代码：

1、迭代堆化

2、迭代的两种写法

def heapify(arr):
    n = len(arr)
    for i in reversed(range(n // 2)):
        shiftDown(arr,n,i)

def shiftDown(arr, n, k):
    while 2 * k + 1 < n:
        j = 2 * k + 1
        if j + 1 < n and arr[j + 1] < arr[j]:
            j += 1
        if arr[k] <= arr[j]:
            break
        arr[k], arr[j] = arr[j], arr[k]
        k = j

def shiftDown2(arr, n, k):
    smallest, l, r = k, 2 * k + 1, 2 * k + 2
    while l < n:
        if arr[l] < arr[smallest]:
            smallest = l
        if r < n and arr[r] < arr[smallest]:
            smallest = r
        if smallest == k:
            break
        else:
            arr[k], arr[smallest] = arr[smallest], arr[k]
            k = smallest
            l, r = 2 * k + 1, 2 * k + 2

def heapSort(arr):
    n=len(arr)
    heapify(arr)
    print("堆化：",arr)
    for i in range(n-1):
        arr[n-i-1],arr[0] = arr[0],arr[n-i-1]
        # print("交换最小值后：",arr)
        shiftDown(arr,n-i-1,0)
        # print("调整后：",arr)


arr = [3,2,1,9,7,8]
heapSort(arr)
print("排序后：",arr)

上面那个就不算堆排序，感觉是强行弄个什么根节点出来，稍微改下有点像归并排序，只不过归并排序是给子序列排序，而这个是每轮循环找出最大值

def OneHeapSort(list, l, r):
    if r-l<=0:
        return
    else:
        middle = l + (r-l-1)//2
        OneHeapSort(list, l, middle)
        OneHeapSort(list, middle+1, r)
        if list[middle]>list[r]:
            list[middle],list[r] = list[r],list[middle]

# 依次将最大值放到数组的后面
def heapSort(list):
    for i in range(len(list)-1, 0, -1):
        OneHeapSort(list, 0, i)


list = [1, 10, 8, 200, 50, 4]
heapSort(list)
print(list) # [1,4,8,10,50,200]

进行堆排序（大根堆）主要解决以下问题：

• 1）构造大根堆；
• 2）交换堆顶元素和最小值；
• 3）重复 2

def help_adjust(L,start,end):
  temp=L[start]
  i=start
  j=2*i
  while j<=end:  # 这里一定要有等于
    if j<end and L[j]<L[j+1]:  # 保证右子树小于左子树
      j+=1
    if temp<L[j]:  # 根节点大于左子树
      L[i]=L[j]
      i=j
      j=2*i
    else:
      break
  L[i]=temp

# 交换堆中元素
def swap_param(L,i,j):
  L[i],L[j]=L[j],L[i]
  return L

def help_sort(L):
  L_length=len(L)-1  # 这里构造的无序列表在最左侧加了一个0用于更好的确定堆顶
  first_sort_count=L_length//2  # 构造辅助变量用于构造大根堆
  for i in range(first_sort_count):
    help_adjust(L,first_sort_count-i,L_length)
   
  for i in range(L_length-1):
    swap_param(L,1,L_length-i)
    help_adjust(L,1,L_length-i-1)

  return [L[i] for i in range(1,len(L))]