配列で最小ヒープを実装する：Minを挿入して削除する（重複して）

Question

JavaでMin Heapを実装しようとしていますが、要素の挿入と削除に問題があります。ルートは分）。ほとんどの場合、ヒープを視覚的に表示するプログラムを使用し、minが削除されたときに新しいルーツを表示しています。

私の問題は、新しいアイテムが追加されたときに何らかの理由でルートが新しいアイテムに切り替わることはありませんが、その理由はわかりません。また、これは重複が多い場合にのみ問題になると思われますが、ヒープは完全に順番にとどまることはできません（親は子よりも小さい）。ほとんどの場合、それはそうです。時にはそれだけではなく、私にとっては無作為に見える。

これはジェネリックで行われ、基本的にほとんどのアルゴリズムに従います。事実について私が知っているものは他にもありますが、これらの2つの方法では間違いなく問題です。

public void insert(T e) { 
    if (size == capacity) 
     increaseSize(); //this works fine 

    last = curr; //keeping track of the last index, for heapifying down/bubbling down when removing min 
    int parent = curr/2; 
    size++; //we added an element, so the size of our data set is larger 


    heap[curr] = e; //put value at end of array 

    //bubble up 
    int temp = curr; 

    while (temp > 1 && ((Comparable<T>) heap[temp]).compareTo(heap[parent]) < 0) { //if current element is less than the parent 
     //integer division 
     parent = temp/2; 
     swap(temp, parent); //the swapping method should be correct, but I included it for clarification 
     temp = parent; //just moves the index value to follow the element we added as it is bubbled up 
    } 

    curr++; //next element to be added will be after this one 


} 

public void swap(int a, int b){ 
    T temp = heap[a]; 
    heap[a] = heap[b]; 
    heap[b] = temp; 
} 


public T removeMin() { 

    //root is always min 
    T min = heap[1]; 

    //keep sure array not empty, or else size will go negative 
    if (size > 0) 
     size--; 

    //put last element as root 
    heap[1] = heap[last]; 
    heap[last] = null; 

    //keep sure array not empty, or else last will not be an index 
    if (last > 0) 
     last--; 

    //set for starting at root 
    int right = 3; 
    int left = 2; 
    int curr = 1; 
    int smaller = 0; 

    //fix heap, heapify down 
    while(left < size && right < size){ //we are in array bounds 

     if (heap[left] != null && heap[right] != null){ //so no null pointer exceptions 
      if (((Comparable<T>)heap[left]).compareTo(heap[right]) < 0) //left is smaller 
       smaller = left; 
      else if (((Comparable<T>)heap[left]).compareTo(heap[right]) > 0) //right is smaller 
       smaller = right; 
      else //they are equal 
       smaller = left; 
     } 
     if (heap[left] == null || heap[right] == null)//one child is null 
     { 
      if (heap[left] == null && heap[right] == null)//both null, stop 
       break; 
      if (heap[left] == null)//right is not null 
       smaller = right; 
      else //left is not null 
       smaller = left; 
     } 


     if (((Comparable<T>)heap[curr]).compareTo(heap[smaller]) > 0)//compare smaller or only child 
     { 
      swap(curr,smaller); //swap with child 
      curr = smaller; //so loop can check new children for new placement 
     } 
     else //if in order, stop 
      break; 

     right = 2*curr + 1; //set new children 
     left = 2*curr; 
    } 


    return min; //return root 
} 

方法で宣言されていないすべての変数がグローバルである、と私は物事のカップルを知っているが、追加で全体の最後の/現在/一時状況のように、おそらく重複しているので、私はそのことについて申し訳ありません。私はすべての名前を自明にし、removeMinで行ったすべてのチェックを説明しようとしました。どんな助けでも大変感謝していますが、私は物事を見てデバッグすることができます。私はここで何かを根本的に欠いていると思う。

Answer 1

デバッグに役立つように、コードを単純化する必要があります。 「最後の」変数には何か変わったことがあります。また、ループを実行するときに 'insert'で、おそらくtempは0になるはずです。

while (temp >= 0 &&......