Java - ヒープベースの優先度キューに関数を実装する方法

Question

プログラミング割り当てのために、私は入力ファイルを読み込んで自己作成の最大ヒープ優先度キューを使ってデータをソートするプログラムの作成に取り組んでいます。データファイルには、「insert [a name] [number]」または「remove」のいずれかの行があります。この優先度キューでは、オブジェクトの挿入と削除のための関数を作成する必要があります。キュー内の各オブジェクトには、文字列としての名前と、整数としての優先順位が含まれています。このヒープは、255のサイズの配列に基づいて実装する必要があります。

私の質問は、私のインサートの実装に問題があり、指定したとおりに機能するために削除しています。私は1）彼らが仕事をする必要がある、2）私が作った擬似コード、そして3）私が実装した実際のJavaコードを提供します。私の機能はどちらも私の意図とまったく同じではありませんので、経験豊富なプログラマーの指示を使うことができます。

1）insert（name、priority）：この関数は文字列型の型と優先度のある型の整数を取り、それらを優先度キューに挿入する必要があります。 remove（）：この関数は、最も優先度の高い値を持つオブジェクトを削除し、オブジェクトから名前の文字列を返す必要があります。

2）バックグラウンドとして、私はこのプログラムのために3つのクラスを持っています：まず、ファイルを読み込み、関数を使用する実装を含む「メイン」クラス。次に、「name」クラス。これは、nameストリングとpriority int、コンストラクター、および2つのオブジェクトの優先順位値を比較するcompareToメソッドを含むnameオブジェクトを作成します。第3に、 "priorityqueue"クラスは、挿入と削除の関数を含んでいます。さて、ここで私は、これらの二つの機能のために作られた擬似コードです：

挿入：

真の入力からオブジェクトを作成した場合

• 配列が一杯になった場合は、チェックは（NUM = 255）、投げます挿入
• 更新NUM（NUM ++）で2つのオブジェクトを交換するためにwhileループを使用しNUM
• でオブジェクトを挿入名の文字列と優先順位のint
• でファイル

削除：

• 保存最初のオブジェクト
• 大きな子と復帰を決定するためにwhileループを使用して最初の
• 更新NUM（num--）
• に最後のオブジェクトを移動しますそれ。

3）これまでのコードは次のとおりです。私の名前クラスが私に問題を与えている場合に備えて、私は自分の名前と優先クラスのクラスを提供します。

プライオリティキュークラス：

public class PriorityQueue 
{ 
int num; //amount of things in array 
int idx; //index of current name object 
Name[] names = new Name[255]; 

public void insert(String name, int priority) 
{ 
    while (num != 255) 
    { 
     Name addName = new Name(name, priority); 
     names[num] = addName; 
     num++; 

     while(idx != 0 || names[idx].CompareTo(names[(idx-1)/2])) 
     { 
      Name temp = names[idx]; 
      names[idx] = names[(idx-1)/2]; 
      names[(idx-1)/2] = temp; 

      idx = (idx-1)/2; 
     } 
    } 
} 

public Name remove() 
{ 
    Name temp2 = names[0]; 
    //Save first element 

    names[0] = names[idx]; 
    //Move last element to first 

    num--; 
    while(idx < Math.max(2*idx+1,2*idx+2)) 
    { 
     if(names[idx].CompareTo(names[(idx-1)/2])) 
       { 
        Name temp3 = names[idx]; 
        names[idx] = names[(idx-1)/2]; 
        names[(idx-1)/2] = temp3; 
       } 
    } 
    return temp2; 
} 

}

名クラス：

public class Name implements Comparable 
{ 
String name; 
int priority; 

public Name(String n, int i) 
{ 
    name = n; 
    priority = i; 
} 

public boolean CompareTo(Name obj) 
{ 
    if(priority < obj.priority) 
    { 
     return false; 
    } 

    else if(priority > obj.priority) 
    { 
     return true; 
    } 

    return true; 
} 
} 

私は、任意の助けに感謝。ありがとう！

Answer 1

いくつかの問題があります。まず、あなたのinsert方法で：

public void insert(String name, int priority) 
{ 
    while (num != 255) 
    { 
     Name addName = new Name(name, priority); 
     names[num] = addName; 
     num++; 

     while(idx != 0 || names[idx].CompareTo(names[(idx-1)/2])) 
     { 
      Name temp = names[idx]; 
      names[idx] = names[(idx-1)/2]; 
      names[(idx-1)/2] = temp; 

      idx = (idx-1)/2; 
     } 
    } 
} 

while (num != 255)があってはなりません。 num == 255かどうかを確認し、例外があれば例外をスローする必要があります。

次に、idxを初期化する必要があります。

 Name addName = new Name(name, priority); 
     names[num] = addName; 
     idx = num; 
     num++; 

そして、あなたのwhile条件は&&ではなく||使用する必要があります：それはあります。そうしないと、スワップ毎回idxをやるあなたremove方法では0

に等しくない：

public Name remove() 
{ 
    Name temp2 = names[0]; 
    //Save first element 

    names[0] = names[idx]; 
    //Move last element to first 

    num--; 
    while(idx < Math.max(2*idx+1,2*idx+2)) 
    { 
     if(names[idx].CompareTo(names[(idx-1)/2]) > 0) 
       { 
        Name temp3 = names[idx]; 
        names[idx] = names[(idx-1)/2]; 
        names[(idx-1)/2] = temp3; 
       } 
    } 
    return temp2; 
} 

あなたはidxが何であるかを知らないので、あなたは、そこにnames[idx]を望んでいません。あなたが欲しい：ここ

names[0] = names[num-1]; // get last item in the heap 

あなたwhile条件が間抜けです。 Math.max(2*idx+1,2*idx+2)は、idxが負でない限り、常に2*idx+2を返します。また、idxも初期化していません。あなたがここに欲しいのです：

idx = 0; 
while (idx < num) 

は今、何をやろうとしているのはnames[idx]は、その子のいずれかよりも小さいかどうかを確認しています。もしそうなら、2人の子供のうち最大のものを選択して交換してください。だから、：

while (idx < num) 
{ 
    int largestChild = idx*2+1; 
    if (largestChild >= num) break; // idx is at a leaf level 
    if (largestChild+1 < num) 
    { 
     // compare the two children 
     if (names[largestChild].compareTo(names[largestChild+1]) < 0) 
     { 
      largestChild = largestChild+1; 
     } 
    } 
    if (names[idx] < names[largestChild]) 
    { 
     // swap, moving the item down 
     temp = names[idx]; 
     names[idx] = names[largestChild]; 
     names[largestChild] = temp; 
     idx = largestChild; 
    } 
    else 
    { 
     // item is in the proper place 
     break; 
    } 
} 

私はidx両方の方法でメソッド・スコープの変数を作ることをお勧め。グローバルにする必要はなく、メソッドをローカルにすることで、既存のコードのように無効な値を使用するよりも、使用前に初期化する必要があります。

NameクラスのCompareTo機能を変更する必要があると思います。 ComparablecompareTo関数が戻らなければならない：

をこのオブジェクトと負の整数、ゼロ、または正の整数に等しい、より小さい、または指定されたオブジェクトよりも大きいです。

だから、あなたが持っている必要があります。

public boolean CompareTo(Name obj) 
{ 
    if(priority < obj.priority) 
    { 
     return -1; 
    } 

    if (priority > obj.priority) 
    { 
     return 1; 
    } 

    return 0; 
}