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 ...グローバル変数で）それを行っています。

それが宿題である場合は、先に進んでください-実行可能ですが、簡単ではありません.