0

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++;
    }
1
  • 1
    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. Oct 17, 2011 at 0:52

3 Answers 3

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.

1

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

1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.