0

特定のオブジェクトのセットを「ヒープ化」するために使用できるヒープ (Max-Heap、最大要素がルートであることを意味します) クラスを作成しています。このヒープの一般的な構造と、さまざまなアルゴリズムを認識しています。現在、一般的なオブジェクトの場合、比較は定義されていません。したがって、2 つのオブジェクト間の比較を定義する必要があります。私の質問は、この比較関数をクラス ヒープまたはクラス オブジェクトで定義する必要があるかどうかです。クラス Heap で定義すると、使用するすべてのデータ構造に対して、効率的ではない比較関数を書き直す必要があります。これは、オブジェクトを少し変更すると、膨大な数の場所で比較が変更される可能性があるためです。では、これはどのように処理されますか？ありがとうございました。

 class Object{
     int value;
     Object (int a) {
         value=a;
     }

     boolean isLessThan(Object a, Object b){
         if (a.value<=b.value){
             return true;
         }
         else return false;
     }
 }

 class Heap{
     Object [] heap=new Object[1000];
     int size=0;
     Heap() {        
     }

     void HeapifyDownwards (int index){
         int left_child=2*index+1;
         int right_child=2*index+2;

         if (size>right_child){
             // both right and left child exist
             Object right= heap[right_child];
             Object left= heap[left_child];
             Object node = heap[index];

             if ((isLessThanEqualTo(right,node)) && (isLessThanEqualTo(left,node))){
                 return;
             }
         }
         else if (size==right_child){
             //only left child exists
         } 
         else {
             // no child exists
         }
     }
 }
4

2 に答える 2

1

Java でこのような処理を行う一般的な方法は、次のいずれかです。

  1. 実装するデータ構造に格納されている要素を制限するComparable、または
  2. ヒープ オブジェクトにコンパレータを格納します (構築時に設定)。

例として、Java API の TreeSet クラスを見てください。

Java は (ほとんどの場合) 静的に型付けされた言語であるため、このようなデータ構造にジェネリックを使用することは非常に一般的であることに注意してください。特定の種類のオブジェクトに対してヒープクラスを機能させたいという欲求は理解できますが、おそらく学ぶ価値はあります。

また、この演習の目的がヒープの仕組みを学ぶことであれば、すばらしいことです。実際に Java アプリケーションのプライオリティ キューが必要な場合、Java には既にPriorityQueueクラスがあります。

于 2012-11-09T06:16:29.683 に答える