迭代版堆排序（以零为起点）

迭代版down函数

def down(pos):
    n = len(h)
    # pos表示父节点，p表示较小的子节点
    p = 2 * pos + 1
    while p < n: 
        # 将p更新为较小的子节点
        rp = p + 1
        if rp < n and h[rp] < h[p]: p = rp
        # 若pos节点的值比p节点大，交换pos节点与p节点
        if h[pos] > h[p]: 
            h[pos], h[p] = h[p], h[pos]
            pos, p = p, 2 * p + 1
            continue
        break 

运行时间（python）

1. 递归版：大约4600ms
2. 迭代版：大约2000ms

参考文献

魔改自python heapq标准库

完整代码

n, m = list(map(int, input().split()))
h = list(map(int, input().split()))

def down(pos):
    n = len(h)
    p = 2 * pos + 1
    while p < n: 
        rp = p + 1
        if rp < n and h[rp] < h[p]: p = rp
        if h[pos] > h[p]: 
            h[pos], h[p] = h[p], h[pos]
            pos, p = p, 2 * p + 1
            continue
        break 

def pop():
    last = h.pop()
    if h:
        res = h[0]
        h[0] = last
        down(0)
        return res
    return last

for i in reversed(range(n//2)): down(i)

for _ in range(m):
    print(pop(), end=' ')