-1

私の問題は、コードが deQueue および enQueue 関数を正しく実装しているように見えるため、機能よりも意味論的です。

reheapDown 関数と reheapUp 関数が正しく使用されていません。問題はヒープ関数にあると思います

package priqueue;

public class Hosheap{
  private Patient[] elements;
  private int numElements;

  public Hosheap(int maxSize)
  {
    elements= new Patient[maxSize];
    numElements=maxSize;
  }

  public void ReheapDown(int root,int bottom)
  {
    int maxChild;
    int rightChild;
    int leftChild;
    leftChild=root*2+1;
    rightChild=root*2+2;

    if (leftChild<=bottom)
    {
      if(leftChild==bottom)
        maxChild=leftChild;
      else
      {
        if(elements[leftChild].getPriority() <= elements[rightChild].getPriority())
          maxChild=rightChild;
        else
          maxChild=leftChild;
      }
      if(elements[root].getPriority()<elements[maxChild].getPriority())
      {
        Swap(root,maxChild);
        ReheapDown(maxChild,bottom);
      }
    }
  }

  public void ReheapUp(int root,int bottom)
  {
    int parent;
    if(bottom>root)
    {
      parent=(bottom-1)/2;
      if(elements[parent].getPriority()<elements[bottom].getPriority())
      {
        Swap(parent,bottom);
        ReheapUp(root,parent);
      }
    }
  }

 public void Swap(int Pos1, int Pos2)
 {
   Patient temp;
   temp = elements[Pos1];
   elements[Pos1]=elements[Pos2];
   elements[Pos2]=temp;
 }

 public Patient getElement(int e)
 {
   return elements[e];
 }

 public void setElement(Patient p, int n)
 {
    elements[n]=p;
 }
}

アイデアは、単純な優先キュー システムを再配置して、患者オブジェクトが削除されたときに、ReheapUp または Down によってキューが正しく再配置されるようにすることですが、これはコードでは実現できません。プライオリティ キュー コードも含める必要がありますか、それとも長すぎますか?

私は NetBeans IDE 6.0.1 を使用しています。

4

3 に答える 3

1

使用要件に応じて、TreeSets に関連する答えはおそらくあなたが望むことをするでしょう。

ただし、並べ替えられたコレクションとは対照的に、キューが本当に必要な場合は、組み込みのPriorityQueueが役立つ場合があります。

于 2009-03-16T12:44:39.313 に答える
0

以下は、PriorityHeap の簡単な実装です。私はそれを非常に迅速にコーディングしたので、いくつかの欠陥があるかもしれませんが、pushUp() および pushDown() ロジックを実装しました。 

import java.util.Random;

public class Heap {

    private Double[] data;
    private int lastItem;

    public Heap(int initialSize) {
        // to simplify child/parent math leave the first index empty
        // and use a lastItem that gives us the size
        data = new Double[initialSize];
        lastItem = 0;
    }

    public void insert(Double d) {
        // double size if needed
        // should have a matching shrink but this is example code
        if (lastItem + 1 >= data.length) {
            Double[] doubled = new Double[data.length * 2];
            System.arraycopy(data, 0, doubled, 0, data.length);
            data = doubled;
        }
        data[lastItem + 1] = d;
        lastItem++;
        pushUp(lastItem);
    }

    public void pushDown(int index) {

        if (lastItem > 1) {

            int leftChildIndex = index * 2;
            int rightChildIndex = leftChildIndex + 1;

            // assume that neither child will dominate (in priority) 
            // the item at index
            int indexToPromote = index;
            // there may not be a left child
            if (leftChildIndex <= lastItem) {

                Double leftChild = data[leftChildIndex];
                Double tmp = data[index];
                if (tmp.compareTo(leftChild) < 0) {
                    indexToPromote = leftChildIndex;
                }

                // there might not be a right child
                if (rightChildIndex <= lastItem) {
                    Double rightChild = data[rightChildIndex];
                    tmp = data[indexToPromote];
                    if (tmp.compareTo(rightChild) < 0) {
                        indexToPromote = rightChildIndex;
                    }
                }
            }

            // did either child dominate the item at index
            // if so swap and push down again
            if (indexToPromote != index) {
                swap(index, indexToPromote);
                pushDown(indexToPromote);
            }
        }
    }

    public void pushUp(int index) {
        if (index > 1) {
            // equivalent to floor((double)index/2.0d);
            // if item at index is greater than its parent
            // push the item up to until if finds a home
            int parentIndex = index >>> 1;
            Double parent = data[parentIndex];
            Double item = data[index];
            if (item.compareTo(parent) > 0) {
                swap(parentIndex, index);
                pushUp(parentIndex);
            }
        }
    }

    public Double removeTop() {
        // assume size is zero then examine other cases
        Double top = null;
        if (lastItem > 1) {
            // save the top item and take the bottom item and place it 
            // at the top the push the new top item down until it 
            // finds a home
            top = data[1];
            Double bottom = data[lastItem];
            lastItem--;
            data[1] = bottom;
            pushDown(1);
        } else if (lastItem == 1) {
            top = data[1];
            lastItem--;
        }
        return top;
    }

    public int size() {
        return lastItem;
    }

    private void swap(int index1, int index2) {
        Double temp = data[index1];
        data[index1] = data[index2];
        data[index2] = temp;
    }

    public static void main(String[] args) {
        Heap heap = new Heap(4);
        Random r = new Random();
        for (int i = 0; i < 100000; i++) {
            Double d = Double.valueOf(r.nextDouble() * 100.0d);
            heap.insert(d);
        }
        double max = Double.MAX_VALUE;
        while (heap.size() > 0) {
            Double top = heap.removeTop();
            if (top.doubleValue() > max) {
                System.out.println("bad ordering...");
            }
            max = top.doubleValue();
            System.out.println(max);
        }
        System.out.println("done...");
    }
}
于 2011-05-19T20:01:22.867 に答える
0

あなたの質問に正確に答えるわけではありませんが、Java では、組み込みの Collection クラスを調べることができます。優先キューの動作を取得できますが、TreeSet (順序付きセットの一種) を使用し、Patient インスタンスのカスタム Comparator を実装します。達成しようとしているものによっては、これが望ましい場合があります。次のようになります。

Patient.java で ...

class Patient implements Comparator { 
...
public int compareTo(Patient other) {
    return getPriority() > other.getPriority() ? 1 : 0;
}

次に、キューを使用する場所で

Set<Patient> queue = new TreeSet<Patient>();
queue.add(p1);
queue.add(p2);
//traverse in order of priority
for(Patient p : queue) {
  doStuff();
}
于 2009-03-16T12:40:09.200 に答える