Removing tail element of priority queue

Question

How can I remove the tail element of a priority queue? I am trying to implement beam search using a priority queue and once the priority queue is full, I want to remove the last element(the element with the least priority).

Thanks!

Solution 1

No easy way. Copy elements from original to new except the last.

PriorityQueue removelast(PriorityQueue pq)
{

    PriorityQueue pqnew;

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

    pq.clear();
    return pqnew;
}

called as

pq = removelast(pq);

Solution 2

You could probably use Guava's MinMaxPriorityQueue to do this. It provides peek, poll, and remove methods for both ends of the queue.

Another option is to write a Queue wrapper that enforces bounding, similar to this answer. You'd need to implement offer, add, and addAll to check capacity. Something like:

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'
}

Solution 3

Use an inverting Comparator and remove from the head. If you need both the head and the tail you are using the wrong data structure.

Solution 4

I think, PR's use case is, that he needs the head, but also want to have a small PQ, so the idea is to remove the tail.

As a PQ is realized as a binary tree mapped to an array, the head is always the first element of the backing array (queue[0]), but the tail is not always at the end of the array, you had to search it.

I think a nice way is to subclass PQ and write the following two methods:

    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;
     }   
    }

Solution 5

While you add the data into priority queue itself do the comparison;

PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());

View more solutions