How to Use a Priorityqueue

How do I use a PriorityQueue?

Use the constructor overload which takes a Comparator<? super E> comparator and pass in a comparator which compares in the appropriate way for your sort order. If you give an example of how you want to sort, we can provide some sample code to implement the comparator if you're not sure. (It's pretty straightforward though.)

As has been said elsewhere: offer and add are just different interface method implementations. In the JDK source I've got, add calls offer. Although add and offer have potentially different behaviour in general due to the ability for offer to indicate that the value can't be added due to size limitations, this difference is irrelevant in PriorityQueue which is unbounded.

Here's an example of a priority queue sorting by string length:

// Test.java
import java.util.Comparator;
import java.util.PriorityQueue;

public class Test {
    public static void main(String[] args) {
        Comparator<String> comparator = new StringLengthComparator();
        PriorityQueue<String> queue = new PriorityQueue<String>(10, comparator);
        queue.add("short");
        queue.add("very long indeed");
        queue.add("medium");
        while (queue.size() != 0) {
            System.out.println(queue.remove());
        }
    }
}

// StringLengthComparator.java
import java.util.Comparator;

public class StringLengthComparator implements Comparator<String> {
    @Override
    public int compare(String x, String y) {
        // Assume neither string is null. Real code should
        // probably be more robust
        // You could also just return x.length() - y.length(),
        // which would be more efficient.
        if (x.length() < y.length()) {
            return -1;
        }
        if (x.length() > y.length()) {
            return 1;
        }
        return 0;
    }
}

Here is the output:

short

medium

very long indeed

How to use pair in a priority queue and then return the value using the key as the priority

You need to use Comparator which will be used to order this priority queue.

Use Comparator.comparing() and pass Method reference of comparing parameter when create the PriorityQueue

PriorityQueue<Pair<Integer,Integer> > pq=
                new PriorityQueue<Pair<Integer,Integer>>(n, Comparator.comparing(Pair::getKey));

Or

You can use lambda expression

PriorityQueue<Pair<Integer,Integer> > pq=
                    new PriorityQueue<Pair<Integer,Integer>>(n,(a,b) -> a.getKey() - b.getKey());

How to use PriorityQueue in TensorFlow?

It seems that according to the comments in priority_queue_v2 in gen_data_flow_ops.py it has to be present.

Args:
shapes: A list of shapes (each a tf.TensorShape or list of ints).
The shape of each component in a value. The length of this attr must
be either 0 or the same as the length of component_types. If the length of
this attr is 0, the shapes of queue elements are not constrained, and
only one element may be dequeued at a time.

It accepts shapes=[()] or shapes=[tf.TensorShape([])] but without that I see the same error.

import tensorflow as tf
import threading

list = tf.placeholder(tf.int64,name="x")


def build_queue():
    with tf.name_scope("Queue"):
        q = tf.PriorityQueue(2,tf.int64,shapes=[()],name="iq",shared_name="queue")
    return q

queue = build_queue()

enqueue_op = queue.enqueue_many([list,list])

dequeue_op = queue.dequeue()

data_batch = tf.train.batch([dequeue_op], batch_size=2, capacity=40)

init_op = tf.group(tf.global_variables_initializer(),
tf.local_variables_initializer(), tf.initialize_local_variables())

sess = tf.Session()

def put():
    sess.run(enqueue_op, feed_dict={list: [1,2,3,4,5]})

mythread = threading.Thread(target=put, args=())
mythread.start()

tf.train.start_queue_runners(sess)

try:
    while True:
        print (sess.run(data_batch))
except tf.errors.OutOfRangeError:
    print ("Queue empty")


sess = tf.Session()
sess.run(tf.global_variables_initializer())
sess.run( build_queue() )

Change priorityQueue to max priorityqueue

How about like this:

PriorityQueue<Integer> queue = new PriorityQueue<>(10, Collections.reverseOrder());
queue.offer(1);
queue.offer(2);
queue.offer(3);
//...

Integer val = null;
while( (val = queue.poll()) != null) {
    System.out.println(val);
}

The Collections.reverseOrder() provides a Comparator that would sort the elements in the PriorityQueue in a the oposite order to their natural order in this case.

Sorting Priority Queue in Java

A PriorityQueue is what is called a binary heap. It is only ordered/sorted in the sense that the first element is the least. In other word, it only cares about what is in the front of the queue, the rest are "ordered" when needed.

The elements are only ordered as they are dequeued, i.e. removed from the queue using poll(). This is the reason why a PriorityQueue manages to have such good performance, as it is not doing any more sorting than it needs at any time.

If you want to know how heaps work in detail I recommend this MIT lecture on heaps.

How do I use a priority queue in c++?

Refer to your documentation and you'll see pop has no return value. There are various reasons for this, but that's another topic.

The proper form is:

while (!s.empty())
{
    int t = s.top();
    s.pop();

    cout << t << endl;
}

Or:

for (; !s.empty(); s.pop())
{
    cout << s.top(); << endl;
}

How to Sort PriorityQueue in Java with class

Your comparator lambda is correct, you can use it as-is. You just need to poll the queue in order to fetch the elements in the correct order:

    while (!pq.isEmpty()) {
      Schedule s = pq.poll();
      System.out.println("income:" + s.income + " " + "time: " + s.date);
    }

Java PriorityQueue: how to heapify a Collection with a custom Comparator?

If you don't mind some hack

According to the java doc of PriorityQueue(PriorityQueue)

Creates a PriorityQueue containing the elements in the specified priority queue. This priority queue will be ordered according to the same ordering as the given priority queue.

So we can extend PriorityQueue as CustomComparatorPriorityQueue to hold the desired comparator and the Collection we need to heapify. Then call new PriorityQueue(PriorityQueue) with an instance of CustomComparatorPriorityQueue.

Below is tested to work in Java 15.

import java.util.*;

public class CustomComparatorPriorityQueue<T> extends PriorityQueue<T> {
    private Collection<T> wrapped;

    public static <U> PriorityQueue<U> create(Collection<U> wrapped, Comparator<U> custom) {
        return new PriorityQueue<U>(new CustomComparatorPriorityQueue<>(wrapped, custom));
    }

    private CustomComparatorPriorityQueue(Collection<T> wrapped, Comparator<T> custom) {
        super(custom);
        this.wrapped = wrapped;
    }

    @Override
    public Object[] toArray() {
        return wrapped.toArray();
    }

    public static void main(String[] args) {
        List<Integer> a = Arrays.asList(3, 6, 4, 8, 1, 9);
        PriorityQueue<Integer> pq = CustomComparatorPriorityQueue.create(a, Comparator.<Integer>naturalOrder().reversed());
        Integer b;
        while ((b = pq.poll()) != null) {
            System.out.println(b);
        }
    }

    // Override to don't allow other purpose...
}

---

Related Topics