• Post Reply Bookmark Topic Watch Topic
  • New Topic

Max priority queue  RSS feed

 
shaurye vardhan
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Guys can you tell me if this is the correct implementation for a max priority queue




import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;


public class MaxPQ<Key> implements Iterable<Key> {
private Key[] pq; // store items at indices 1 to N
private int N; // number of items on priority queue
private Comparator<Key> comparator; // optional Comparator


public MaxPQ(int initCapacity) {
pq = (Key[]) new Object[initCapacity + 1];
N = 0;
}
public MaxPQ() {
this(1);
}


public MaxPQ(int initCapacity, Comparator<Key> comparator) {
this.comparator = comparator;
pq = (Key[]) new Object[initCapacity + 1];
N = 0;
}

public MaxPQ(Comparator<Key> comparator) {
this(1, comparator);
}

public MaxPQ(Key[] keys) {
N = keys.length;
pq = (Key[]) new Object[keys.length + 1];
for (int i = 0; i < N; i++)
pq[i+1] = keys[i];
for (int k = N/2; k >= 1; k--)
sink(k);
assert isMaxHeap();
}



public boolean isEmpty() {
return N == 0;
}


public int size() {
return N;
}


public Key max() {
if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");
return pq[1];
}


private void resize(int capacity) {
assert capacity > N;
Key[] temp = (Key[]) new Object[capacity];
for (int i = 1; i <= N; i++) temp[i] = pq[i];
pq = temp;
}


public void insert(Key x) {

// double size of array if necessary
if (N >= pq.length - 1) resize(2 * pq.length);

// add x, and percolate it up to maintain heap invariant
pq[++N] = x;
swim(N);
assert isMaxHeap();
}


public Key delMax() {
if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");
Key max = pq[1];
exch(1, N--);
sink(1);
pq[N+1] = null; // to avoid loiterig and help with garbage collection
if ((N > 0) && (N == (pq.length - 1) / 4)) resize(pq.length / 2);
assert isMaxHeap();
return max;
}


private void swim(int k) {
while (k > 1 && less(k/2, k)) {
exch(k, k/2);
k = k/2;
}
}

private void sink(int k) {
while (2*k <= N) {
int j = 2*k;
if (j < N && less(j, j+1)) j++;
if (!less(k, j)) break;
exch(k, j);
k = j;
}
}

private boolean less(int i, int j) {
if (comparator == null) {
return ((Comparable<Key>) pq[i]).compareTo(pq[j]) < 0;
}
else {
return comparator.compare(pq[i], pq[j]) < 0;
}
}

private void exch(int i, int j) {
Key swap = pq[i];
pq[i] = pq[j];
pq[j] = swap;
}

// is pq[1..N] a max heap?
private boolean isMaxHeap() {
return isMaxHeap(1);
}

// is subtree of pq[1..N] rooted at k a max heap?
private boolean isMaxHeap(int k) {
if (k > N) return true;
int left = 2*k, right = 2*k + 1;
if (left <= N && less(k, left)) return false;
if (right <= N && less(k, right)) return false;
return isMaxHeap(left) && isMaxHeap(right);
}

public Iterator<Key> iterator() { return new HeapIterator(); }

private class HeapIterator implements Iterator<Key> {

// create a new pq
private MaxPQ<Key> copy;


public HeapIterator() {
if (comparator == null) copy = new MaxPQ<Key>(size());
else copy = new MaxPQ<Key>(size(), comparator);
for (int i = 1; i <= N; i++)
copy.insert(pq[i]);
}

public boolean hasNext() { return !copy.isEmpty(); }
public void remove() { throw new UnsupportedOperationException(); }

public Key next() {
if (!hasNext()) throw new NoSuchElementException();
return copy.delMax();
}
}

public static void main(String[] args) {
MaxPQ<String> pq = new MaxPQ<String>();
while (!StdIn.isEmpty()) {
String item = StdIn.readString();
if (!item.equals("-")) pq.insert(item);
else if (!pq.isEmpty()) StdOut.print(pq.delMax() + " ");
}
StdOut.println("(" + pq.size() + " left on pq)");
}

}
 
Campbell Ritchie
Marshal
Posts: 56595
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What is the behaviour of a priority queue? What are the class' invariants? What efforts have you taken to prove that it maintains those invariants and behaves as you want it to? What happens if you pass nulls? What happens if you empty the queue? What happens if you supply more elements than the current size of the array?

You cannot expect to supply lots of unformatted code and have us read it and tell you whether it is a correct implementation.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!