key in java - priority queue

Question

I am trying to learn java and I am stumped by this example- I can't find what the key is

public class OrderedArrayMaxPQ<Key extends Comparable<Key>> {
    private Key[] pq;          // elements

This is the example of the priority queue .. i got it from http://algs4.cs.princeton.edu/24pq/OrderedArrayMaxPQ.java.html I thought a priority queue should have a data + a priority value. I am not sure how these guys are doing it.

public class OrderedArrayMaxPQ<Key extends Comparable<Key>> {
    private Key[] pq;          // elements
    private int N;             // number of elements

    // set inititial size of heap to hold size elements
    public OrderedArrayMaxPQ(int capacity) {
        pq = (Key[]) (new Comparable[capacity]);
        N = 0;
    }


    public boolean isEmpty() { return N == 0;  }
    public int size()        { return N;       } 
    public Key delMax()      { return pq[--N]; }

    public void insert(Key key) {
        int i = N-1;
        while (i >= 0 && less(key, pq[i])) {
            pq[i+1] = pq[i];
            i--;
        }
        pq[i+1] = key;
        N++;
    }

Just to note, if you intend on using this code in a production environment, you should be aware that there will be an Unchecked Conversion warning on the array construction line which is unfortunately unavoidable, but I would recommend using a @SuppressWarnings annotation for. Also (and probably more importantly), the delMax() method fails to null out the no-longer-used reference, which may prevent keys that have been removed from the queue from being garbage collected. — Daniel Pryden
– Daniel Pryden, Commented Oct 17, 2011 at 0:52

Dave Newton · Accepted Answer · 2011-10-16 23:41:17Z

2

The priority is implemented within the Key implementation via its Comparable interface.

In the example you link to, they use String elements, so the priority is String's implementation of Comparable.

If you wanted to implement, say, a numeric priority, you'd create a priority queue with your class, which would implement Comparable, comparing the numeric value of the priority field.

answered Oct 16, 2011 at 23:41

Dave Newton

161k27 gold badges263 silver badges310 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

user207421 · Accepted Answer · 2011-10-17 03:34:09Z

1

You don't need Key[], just Comparable[].

answered Oct 17, 2011 at 3:34

user207421

312k45 gold badges324 silver badges493 bronze badges

Comments

jayunit100 · Accepted Answer · 2011-10-17 05:19:29Z

Like the others say, focus on the comparable interface. A good way to get a feel for how java implements priority queues is to note the fact that String, Integer, Float, and other classes implement the Comparator interface.

This means that , by the objects definition, it is comparable (<,>, or =) to other objects of the same type.

I would suggest , rather than learning about priority queues, you

1) play with the sorting of simpler java data structures like Vectors and TreeMaps. 2) Look through the Collections API. Write a program which, for example, uses Collections.sort to sort some different lists.
3) Try to write an object which implements the Comparator interface, and sort a collection of these objects.

Collectives™ on Stack Overflow

key in java - priority queue

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related