递归如何在堆排序中工作？

Question

假设我有一个数组 A = <1,6,2,7,3,8,4,9,5> Heapsort 的伪代码：

BUILD-MAX-HEAP(A)
n = A.heapsize = A.length
for i = floor(n/2) down to 1
   MAX-HEAPIFY(A,i)

MAX-HEAPIFY(A,i)
n = A.heap-size
l = LEFT(i)
r = RIGHT(i)
if l <= n and A[l] > A[i]
   largest = l
if r <= n and A[r] > A[largest]
   largest = r
if largest != i
   exchange A[i] <-> A[largest]
   MAX-HEAPIFY(A,largest)

我知道 BUILD-MAX-HEAP 会先调用 MAX-HEAPIFY(A,4)，它会交换 7 和 9，然后在 MAX-HEAPIFY (A,3) 之后它会交换 8 和 2。然后它将调用 MAX-HEAPIFY(A,2)，这是我感到困惑的地方。这是调用 MAX-HEAPIFY(A,2) 时堆的样子

首先会发生的事情是6和7交换，然后调用MAX-HEAPIFY(A,4)（因为4现在是最大的），交换6和9，然后调用MAX-HEAPIFY(A,8) 但是什么都不会发生，因为你已经到达了一片叶子，所以它 return 到调用它的函数。

MAX-HEAPIFY(A-8) 被 MAX-HEAPIFY(A,4) 调用，所以它 return 到它

MAX-HEAPIFY(A,4) 被 MAX-HEAPIFY(A,2) 调用，所以它 return 到它

但现在 A[2] < A[4]（因为 7 < 9），正是在这一点上，我想知道它是如何知道再次调用 MAX-HEAPIFY(A,2) 来交换 7 和9. 当一个递归函数（或子程序）returns 到调用它的函数时，没有更多的代码要执行（因为 MAX-HEAPIFY 只在函数末尾调用 MAX-HEAPIFY），所以它将 return 备份递归堆栈，在我看来，7 仍然是 9

的父级

抱歉，如果这让我感到困惑，但有人可以引导我完成这个过程以帮助我理解这究竟是如何递归地最大堆化自身的吗？

Answer 1

以下是我在遵循您的算法时得到的一系列步骤（注意我们在每个末尾递归时的缩进级别）。每次我们退出该函数时，我们只是 return 到主程序（调用 max_heapify 并将数字 4 降到 1）。我不确定你的解释哪里不对，但我希望下面的内容能让它更清楚。

for i in (4,3,2,1):
    MAX-HEAPIFY(A,i)

MAX-HEAPIFY(A,4):
    largest=4  # initialized
    l=8
    r=9
    largest=8  # calculated
    swap A[4] and a[8]:
    A = <1,6,2,9,3,8,4,7,5>
    MAX-HEAPIFY(A, 8):
        largest=8  # initialized
        l=16
        r=17
        ...return
    ...return

MAX-HEAPIFY(A,3):
    largest=3  # initialized
    l=6
    r=7
    largest=6  # calculated
    swap A[3] and A[6]:
    A = <1,6,8,9,3,2,4,7,5>
    MAX-HEAPIFY(A, 6):
        largest=6
        l=12
        r=13
        ...return
    ...return

MAX-HEAPIFY(A,2):
    largest=2 # initialized
    l=4
    r=5
    largest=4 # calculated
    swap A[2]and A[4]:
    A = <1,9,8,6,3,2,4,7,5>
    MAX-HEAPIFY(A, 4):
        largest=4  # initialized
        l=8
        r=9
        largest=8
        swap A[4] and A[8]:
        A = <1,9,8,7,3,2,4,6,5>
        MAX-HEAPIFY(A, 8):
            largest=8  # initialized
            l=16
            r=17
            ...return
        ...return
     ...return

MAX-HEAPIFY(A,1):
    largest=1  # initialized
    l=2
    r=3
    largest=2  # calculated
    swap A[1] and A[2]:
    A = <9,1,8,7,3,2,4,6,5>
    MAX-HEAPIFY(A, 2):
        largest=2:  # initialized
        l=4
        r=5
        largest=4:  # calculated
        swap A[2] and A[4]:
        A = <9,7,8,1,3,2,4,6,5>
        MAX-HEAPIFY(A, 4):
            largest=4:  # initialized
            l=8
            r=9
            largest=8:  # calculated
            swap A[4] and A[8]:
            A = <9,7,8,6,3,2,4,1,5>
            MAX-HEAPIFY(A, 8):
                largest=8:  # initialized
                l=16
                r=17        
                ...return
            ...return
        ...return
    ...return

Done!
A = <9,7,8,6,3,2,4,1,5>

然后我甚至将你的算法（几乎直接）翻译成 python（注意我必须对 python 的基于 0 的索引进行一些调整）：

def build_max_heap(A):
    for i in range(len(A)//2, 0, -1): 
        max_heapify(A, i)

def left(x):
    return 2 * x

def right(x):
    return 2 * x + 1


def max_heapify(A, i):
    n = len(A)
    largest = i
    l = left(i)
    r = right(i)
    if l<=n and A[l-1] > A[i-1]:
        largest = l
    if r <=n and A[r-1] > A[largest-1]:
        largest = r
    if largest !=i:
        A[i-1], A[largest-1] = A[largest-1], A[i-1]
        max_heapify(A,largest)

if __name__ == '__main__':
    A = [1,6,2,7,3,8,4,9,5]
    build_max_heap(A)  # modifies in-place
    print(A)

这会打印： [9, 7, 8, 6, 3, 2, 4, 1, 5] （这与我们的手动迭代一致）

...再进行一次检查，使用 python 的 heapq 模块及其私有方法 _heapify_max:

import heapq
A = [1,6,2,7,3,8,4,9,5]
heapq._heapify_max(A)
print(A)

...打印相同的内容： [9, 7, 8, 6, 3, 2, 4, 1, 5]

递归如何在堆排序中工作？

How does the recursion work in heap-sort?

recursion

heapsort