python - 我的堆工作太慢

Question

所以这是我的最小堆代码。这是我作业的一部分：

def heapify(i):
    global end,a
    l=2*i+1        
    if l>end:
        return None
    r=2*i+2
    minarg=i        
    if a[i]>a[l]:
        minarg=l
    if r<=end:
        if a[minarg]>a[r]: minarg=r
    if a[i]==a[minarg]:
        return None
    else:
        a[i],a[minarg]=a[minarg], a[i]
        heapify(minarg)

def buildHeap(start):
    global end,a
    if start*2+1>end:
        return None
    buildHeap(start*2+1)
    buildHeap(start*2+2)
    heapify(start)

它应该可以工作，但是对于大型测试用例，我超出了时间限制。难道我做错了什么？

Answer 1

Python 中的函数调用需要时间，递归需要空间。

为了节省递归的时间，通常将其转换为循环。这通常需要使用专门的日期“内存管理”来处理安全空间。您已经使用数组/列表（使用... ehem ... 全局变量）做到了这一点。

如果这是你的功课，那就继续吧——可行，但不重要。