最小ヒープアルゴリズム

Question

この予想通り、私のminheapアルゴリズムは、しかし、それが機能していないです：データ要素は、様々な順序で追加されたアルゴリズムが正しくないminHeapsを返し

public static int [] fixheap(int heap[], int n, int i){ 
    int j=2*i; 
    int weight = heap[i]; 

    while (j<=n){ 
     if((j<n) && heap[j] > heap[j+1]) 
      j++; 
     if(weight <= heap[j]) break; 
     else 
     heap[j/2] = heap[j]; 

     j=j*2; 
    } 

    heap[j/2]= weight; 

    return heap; 
} 

public static void makeheap(int heap[], int n){ 

    for (int i=n/2; i>=0; i--){ 
     fixheap(heap, n ,i); 
    } 
} 

。誰もこの最小ヒープアルゴリズムの明らかな問題を見ることができますか？

Answer 1

ヒープを形成するために配列の間違った要素を比較しています。あなたのプログラムを乾かしてみてください

配列はインデックス0から始まるので、最初はここでi = n/2-1とします。

public static void makeheap(int heap[], int n){ 

    for (int i=n/2 - 1; i>=0; i--){ 
    fixheap(heap, n ,i); 
    } 
} 

そして、あなたが持っているでしょうが、私は道あなたが親を見つけていることを信じてい

J = i *は2 + 1

Answer 2

jについて正しい値を得るためにあなたのfixheap機能を変更します/または子供たちが間違っている。

左の子供がindex1、右がindex2の場合、どうすればindex0に行くのですか？

index0の子供（index1とindex2）を見つけることはどうですか？

Answer 3

folllwingコードはPythonであるが、私は、重労働を行う行を選択し、その過程でうまくいけば、上記の例では分ヒープ

heapArray = [] 
for heapKey in someArray: 
    insert(heapArray, int(heapKey)) 
return heapArray; 

def insert(heapArray, heapKey): 
    heapArray.append(heapKey) 
    index_of_key = len(heapArray)-1 
    parent_index_of_key = (index_of_heap_key-1)/2 
    while index_of_key>0: 
    if(heapKey < heapArray[parent_index_of_key]): 
     __swap(index_of_key, parent_index_of_key, heapArray) 
     index_of_key = parent_index_of_key; 
     parent_index_of_key = (index_of_key-1)/2 
    else: 
     break # we have reached the right spot 

を作成する別の解決策を提示しますヒープを再作成します（これはメモリを増やすことを意味しますが、説明のためにこれは良いスタートかもしれません）。ヒープを作成するときは、新しく挿入されたキーの値を親（parent_index_of_keyを介して）でチェックするだけです。

親が子より大きい場合は、値をスワップし、インデックス（スワップされたキーとその新しい親の両方）を更新します。ヒープの先頭に到達するまで、またはヒープキーがチェーンの上に行くことができなくなるまで、そのプロセスを繰り返します。

インプレーススワップは明らかに効率的ですが、上記はより直感的で簡単ですに従う。明らかに、私は上記のコードを使用しません。ここではメモリは大きな制約ですが、コードの簡潔さと明快さがメモリ使用率を凌駕するケースでは考慮しています。