java - プライオリティ キューの末尾要素の削除

Question

プライオリティ キューの末尾要素を削除するにはどうすればよいですか? 優先度キューを使用してビーム検索を実装しようとしていますが、優先度キューがいっぱいになったら、最後の要素 (優先度が最も低い要素) を削除したいと考えています。

ありがとう！

Answer 1

簡単な方法はありません。最後を除いて、要素を元の要素から新しい要素にコピーします。

PriorityQueue removelast(PriorityQueue pq)
{

    PriorityQueue pqnew;

    while(pq.size() > 1)
    {
        pqnew.add(pq.poll());
    }

    pq.clear();
    return pqnew;
}

と呼ばれる

pq = removelast(pq);

Answer 2

これを行うには、おそらく Guava のMinMaxPriorityQueueを使用できます。キューの両端にpeek、poll、およびremoveメソッドを提供します。

別のオプションは、この回答と同様に、境界を強制する Queue ラッパーを作成することです。容量を確認するofferには、 、add、およびを実装する必要があります。addAll何かのようなもの：

public class BoundedQueue<E> implements Serializable, Iterable<E>, Collection<E>, Queue<E> {
    private final Queue<E> queue;
    private int capacity;

    public BoundedQueue(Queue<E> queue, int capacity) {
        this.queue = queue;
        this.capacity = capacity;
    }

    @Override
    public boolean offer(E o) {
        if (queue.size() >= capacity)
            return false;
        return queue.add(o);
    }

    @Override
    public boolean add(E o) throws IllegalStateException {
        if (queue.size() >= capacity)
            throw new IllegalStateException("Queue full"); // same behavior as java.util.ArrayBlockingQueue
        return queue.add(o);
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {
        boolean changed = false;
        for (E o: c)
            changed |= add(o);
        return changed;
    }

    // All other methods simply delegate to 'queue'
}

Answer 3

反転コンパレータを使用し、ヘッドから取り外します。頭と尾の両方が必要な場合は、間違ったデータ構造を使用しています。

Answer 4

PR の使用例は、ヘッドが必要であるが、小さな PQ も必要であるため、テールを削除するという考えです。

PQ は配列にマッピングされたバイナリ ツリーとして実現されるため、先頭は常にバッキング配列の最初の要素 ( queue[0]) ですが、末尾は常に配列の末尾にあるとは限らないため、検索する必要がありました。

PQ をサブクラス化し、次の 2 つのメソッドを記述するのが良い方法だと思います。

    public class MyPriorityQueue<E> extends PriorityQueue<E>
    {
        // constructors

    public E getTail()
     {
        // queue.length can be bigger than this.size() !!
        Object[] queue = this.toArray();
        E tail = (E)queue[0];
        Comparator<? super E> comparator = this.comparator();
        if (comparator !=null)
           for(int i = 1; i < this.size(); i++)
              if ( comparator.compare(tail, (E)queue[i]) < 0)
                 tail = (E)queue[i];
        else
           for(int j = 1; j < this.size(); j++)
              if ( ((Comparable)tail).compareTo( ((Comparable)queue[j]) ) < 0 )
                 tail = (E)queue[j];
        return tail;
     }  

     public E removeTail()
     {
        E tail = this.getTail();
        this.remove(tail);
        return tail;
     }   
    }