heapsortのheapifyを使用してヒープを2つのサブヒープに分割する方法はありますか？

Question

私はtriyngで、PythonでHeapSort関数を作成しています。

私は私の本の指示に従うことをしよう、とのルールに従っていないノードとヒープに正しい順序を復元fixHeapのようないくつかの機能を使用しています：

今

def getMaxKnot(i,j,A): 
    k = max(A[i],A[j]) 
    if k==A[i]: 
     return i 
    if k==A[j]: 
     return j 


def fixheap(v,H): #basically restore an heap with a node not following heap rules 
    if (2*v+1)>len(H)-1: 
     return H 
    else: 
     u=getMaxKnot(2*v+1,2*v+2,H) 
     if H[u]>H[v]: 
      listoperations.swap(u,v,H) #swap item in position u and v 
     return fixheap(u,H) 

、私は基本的に作成したいです私の関数fixheapを使用して正しい順序を復元するために、左ツリーおよび右ツリーで再帰的に機能するheapify関数。

def heapify(A): 
     if A==[]: 
      return A 
     else: 
      heapify(LEFT TREE) 
      heapify(RIGHT TREE) 
      fixheap(0,A) 

LEFT TREEとRIGHT TREEに私のアレイAを分割する方法上の任意のアイデア：

私の考えは以下の通りでしたか？

Answer 1

まず、fixheapに何かがありません。ノードvが1つの（左）子しか持たないと仮定した場合、jはA配列の終わりを超えているため、無効なインデックスエラーを発生させます。getMaxKnot

個人的には、私はgetMaxKnotは別個の機能であるとは思わない。私はfixheapの引数を逆の順序で入れて、2番目の引数を簡単に省略して、デフォルト値（ルート要素の場合）を与えます。また、2つの値を交換することは、本当にワンライナーです：

def fixheap(H, v = 0): # put arguments in this order 
    u = 2*v + 1 
    if u >= len(H): 
     return H 
    if u+1 < len(H) and H[u+1] > H[u]: # Only compare when there are two child nodes 
     u += 1 
    if H[u] > H[v]: 
     [H[u], H[v]] = [H[v], H[u]] # Swapping is easy 
     return fixheap(H, u) 

次に、あなたの主な質問に：あなたのheapifyはまた、あなたがheapifyしたいサブツリーのルートだろう引数としてノードを取得する必要があります。この原理は、実際にはfixheap関数の使用方法とほとんど変わりません。

def heapify(H, v = 0): 
    u = 2*v + 1 
    if u >= len(H): 
     return H 
    heapify(H, u) 
    if u + 1 < len(H): # make sure there is a right child 
     heapify(H, u+1) 
    fixheap(H, v)