迭代HeapSort，但仅更改一个函数（heapify）

Question

有人能帮我更改函数def heapify(arr, heapSize, k)的代码，使之成为Iterative而不是递归的吗？我无法理解，因为它更倾向于只更改一个函数的代码，而不更改其他函数的代码。 代码：

def heapify(arr, heapSize, k):
    smallest = k  # root
    l = 2 * k + 1  # left son
    r = 2 * k + 2  # right  son
    while True:
        if l < heapSize and arr[l] < arr[k]:
            smallest = l
        else:
            smallest = k
        if r < heapSize and arr[r] < arr[smallest]:
            smallest = r
        if smallest != k:
            arr[k], arr[smallest] = arr[smallest], arr[k]
            heapify(arr, heapSize, smallest)
        return arr


def buildHeap(arr):
    o = int((len(arr) - 2) / 2)

    for k in range(o, -1, -1):
        heapify(arr, heapSize, k)
    return arr


def heapSort(arr):
    arr = buildHeap(arr)
    heapSize = len(arr)
    for i in range(len(arr) - 1, 0, -1):
        arr[0], arr[heapSize - 1] = arr[heapSize - 1], arr[0]
        heapSize -= 1
        heapify(arr, heapSize, 0)
    return arr

arr = [10, 20, 15, 17, 9, 21]
heapSize = len(arr)
heapSort(arr)
print(arr)

Answer 1

使heapify迭代不需要太多的更改，因为唯一的递归调用几乎是tail call；递归调用是函数的最后一个操作（可以将return arr视为对heapify的递归调用的“之后”，但返回值在代码中的任何地方都没有使用）

对于尾部调用，您无需担心创建显式堆栈，只需使用带有标志的while循环（或者，使用break），并用对相关变量的写入来替换实际调用。每个循环对应于原始函数中的另一个递归调用，因此请确保在循环中重新初始化所有变量

考虑到这一点，下面是如何将heapify修改为迭代的：

def heapify(arr, heapSize, k):
    done = False

    while not done:
        smallest = k  # root
        l = 2 * k + 1  # left
        r = 2 * k + 2  # right

        if l < heapSize and arr[l] < arr[k]:
            smallest = l
        else:
            smallest = k
        if r < heapSize and arr[r] < arr[smallest]:
            smallest = r

        if smallest != k:
            arr[k], arr[smallest] = arr[smallest], arr[k]
            k = smallest
        else:
            done = True