堆排序比较次数统计异常，请求排查计数逻辑错误

我编写了带有比较次数统计功能的堆排序相关代码，包含max_heapify、build_max_heap和heap_sort函数。调用测试代码lst = [0,1,2,3,4,5,6,7,8,9]执行heap_sort时，预期输出比较次数为41，但实际得到135，请问我的计数逻辑哪里出错了？

原代码： #

def max_heapify(a, n, i):
    count = 0
    l, r = 2*i+1, 2*i+2
    largest = i
    if l < n and a[l] > a[largest]:
        largest = l
    if r < n and a[r] > a[largest]:
        largest = r
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        count += 1
        count += max_heapify(a, n, largest)
    count += 3
    return count


def build_max_heap(a):
    n = len(a)
    count = 0
    for i in range(n//2-1, -1, -1):
        count += max_heapify(a, n, i)
    return count


def heap_sort(a):
    n = len(a)
    count = build_max_heap(a)
    for i in range(n-1, 0, -1):
        a[0], a[i] = a[i], a[0]
        count += 1
        count += max_heapify(a, i, 0)
    return count

测试调用代码： #

lst = [0,1,2,3,4,5,6,7,8,9]
print(heap_sort(lst))

错误点分析 #

1. 无差别累加固定值：max_heapify里的count +=3完全错误，不管实际发生了几次元素比较，都强制加3。实际上我们只需要统计元素大小比较的次数，索引判断（l <n、r <n）不属于排序比较范畴，无需统计。
2. 将交换操作计入比较次数：代码里把交换元素的操作（count +=1）也算进了比较次数，交换是赋值操作，和比较无关，这部分计数必须去掉。
3. 未精准统计每次元素比较：原代码中if条件里的a[l] > a[largest]和a[r] > a[largest]才是真正的排序比较，需要每执行一次就加1，而不是笼统累加。

修正后的代码 #

def max_heapify(a, n, i):
    count = 0
    l, r = 2*i+1, 2*i+2
    largest = i
    # 统计左孩子与当前节点的比较
    if l < n:
        count += 1
        if a[l] > a[largest]:
            largest = l
    # 统计右孩子与当前最大节点的比较
    if r < n:
        count += 1
        if a[r] > a[largest]:
            largest = r
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        # 递归调用时累加后续的比较次数
        count += max_heapify(a, n, largest)
    return count


def build_max_heap(a):
    n = len(a)
    count = 0
    for i in range(n//2-1, -1, -1):
        count += max_heapify(a, n, i)
    return count


def heap_sort(a):
    n = len(a)
    count = build_max_heap(a)
    for i in range(n-1, 0, -1):
        a[0], a[i] = a[i], a[0]
        # 交换操作不统计，直接累加堆调整的比较次数
        count += max_heapify(a, i, 0)
    return count

执行修正后的代码，测试用例输出即为预期的41。

内容的提问来源于stack exchange，提问作者mmm