diff --git a/tools/api-checker/config/gwt27_28userApi.conf b/tools/api-checker/config/gwt27_28userApi.conf
index 1b40f2d..297e668 100644
--- a/tools/api-checker/config/gwt27_28userApi.conf
+++ b/tools/api-checker/config/gwt27_28userApi.conf
@@ -218,4 +218,8 @@
 java.util.AbstractQueue::offer(Ljava/lang/Object;) MISSING
 java.util.AbstractQueue::peek() MISSING
 java.util.AbstractQueue::poll() MISSING
-java.util.AbstractSequentialList::size() MISSING
\ No newline at end of file
+java.util.AbstractSequentialList::size() MISSING
+
+# Removed some JRE incompatible PriorityQueue APIs
+java.util.PriorityQueue::makeHeap(I) MISSING
+java.util.PriorityQueue::mergeHeaps(I) MISSING
\ No newline at end of file
diff --git a/user/super/com/google/gwt/emul/java/util/PriorityQueue.java b/user/super/com/google/gwt/emul/java/util/PriorityQueue.java
index 90480b8..a493491 100644
--- a/user/super/com/google/gwt/emul/java/util/PriorityQueue.java
+++ b/user/super/com/google/gwt/emul/java/util/PriorityQueue.java
@@ -17,7 +17,9 @@
 
 import static javaemul.internal.InternalPreconditions.checkArgument;
 import static javaemul.internal.InternalPreconditions.checkCriticalNotNull;
+import static javaemul.internal.InternalPreconditions.checkElement;
 import static javaemul.internal.InternalPreconditions.checkNotNull;
+import static javaemul.internal.InternalPreconditions.checkState;
 
 /**
  * An unbounded priority queue based on a priority heap.
@@ -80,14 +82,12 @@
 
   @SuppressWarnings("unchecked")
   public PriorityQueue(PriorityQueue<? extends E> c) {
-    // TODO(jat): better solution
     this(c.size(), (Comparator<? super E>) c.comparator());
     addAll(c);
   }
 
   @SuppressWarnings("unchecked")
   public PriorityQueue(SortedSet<? extends E> c) {
-    // TODO(jat): better solution
     this(c.size(), (Comparator<? super E>) c.comparator());
     addAll(c);
   }
@@ -96,7 +96,12 @@
   public boolean addAll(Collection<? extends E> c) {
     checkNotNull(c);
     checkArgument(c != this);
-    if (heap.addAll(c)) {
+
+    int oldSize = heap.size();
+    for (E e : c) {
+      heap.add(checkCriticalNotNull(e));
+    }
+    if (oldSize != heap.size()) {
       makeHeap(0);
       return true;
     }
@@ -114,39 +119,33 @@
 
   @Override
   public boolean contains(Object o) {
-    return indexOf(o) >= 0;
-  }
-
-  @Override
-  public boolean containsAll(Collection<?> c) {
-    return heap.containsAll(c);
+    return indexOf(o) != -1;
   }
 
   @Override
   public Iterator<E> iterator() {
     return new Iterator<E>() {
-      private E current = null;
-      // Make a copy of the elements so that remove() doesn't screw up the order.
-      Iterator<E> elementsToTraverse = new ArrayList<>(heap).iterator();
+      int i = 0, last = -1;
+
       @Override
       public boolean hasNext() {
-        return elementsToTraverse.hasNext();
+        return i < heap.size();
       }
 
       @Override
       public E next() {
-        current = elementsToTraverse.next();
-        return current;
+        checkElement(hasNext());
+
+        last = i++;
+        return heap.get(last);
       }
 
       @Override
       public void remove() {
-        if (current == null) {
-          throw new IllegalStateException("remove() called before iteration or removed already.");
-        }
-        // Remove the current element. Keep on iterating.
-        PriorityQueue.this.remove(current);
-        current = null;
+        checkState(last != -1);
+
+        removeAtIndex(i = last);
+        last = -1;
       }
     };
   }
@@ -238,7 +237,7 @@
    *
    * @param node
    */
-  protected void makeHeap(int node) {
+  private void makeHeap(int node) {
     if (isLeaf(node)) {
       // leaf node are automatically valid heaps
       return;
@@ -259,7 +258,7 @@
    * 
    * @param node the parent of the two subtrees to merge
    */
-  protected void mergeHeaps(int node) {
+  private void mergeHeaps(int node) {
     int heapSize = heap.size();
     E value = heap.get(node);
     while (!isLeaf(node, heapSize)) {
@@ -296,6 +295,10 @@
     return isLeaf(node, heap.size());
   }
 
+  /**
+   * This method leaves the elements at up to i-1, inclusive, untouched.
+   * This information is used by PriorityQueue iterator implementation.
+   */
   private void removeAtIndex(int index) {
     // Remove the last element; put it in place of the really removed element.
     E lastValue = heap.remove(heap.size() - 1);
diff --git a/user/test/com/google/gwt/emultest/java/util/PriorityQueueTest.java b/user/test/com/google/gwt/emultest/java/util/PriorityQueueTest.java
index 4f10055..abed20f 100644
--- a/user/test/com/google/gwt/emultest/java/util/PriorityQueueTest.java
+++ b/user/test/com/google/gwt/emultest/java/util/PriorityQueueTest.java
@@ -15,13 +15,12 @@
  */
 package com.google.gwt.emultest.java.util;
 
-import com.google.gwt.junit.client.GWTTestCase;
+import org.apache.commons.collections.TestCollection;
 
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collection;
 import java.util.Comparator;
-import java.util.Iterator;
 import java.util.NoSuchElementException;
 import java.util.PriorityQueue;
 import java.util.TreeSet;
@@ -29,12 +28,7 @@
 /**
  * Test PriorityQueue.
  */
-public class PriorityQueueTest extends GWTTestCase {
-
-  @Override
-  public String getModuleName() {
-    return "com.google.gwt.emultest.EmulSuite";
-  }
+public class PriorityQueueTest extends TestCollection {
 
   public void testAdd() {
     PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
@@ -65,6 +59,7 @@
       fail();
     } catch (NullPointerException expected) {
     }
+    assertTrue(Arrays.asList(1).containsAll(queue));
 
     queue = new PriorityQueue<>();
     queue.addAll(Arrays.asList(2, 1, 3));
@@ -248,38 +243,31 @@
     return pq;
   }
 
-  public void testIteratorRemove() {
-    PriorityQueue<Integer> queue = new PriorityQueue<>();
-    queue.add(1);
-    queue.add(2);
-    queue.add(3);
-    queue.add(5);
-    queue.add(6);
+  /**
+   * Null elements are prohibited in PriorityQueue.
+   */
+  @Override
+  protected Object[] getFullElements() {
+    return new Integer[] {1, 2, 3, 4};
+  }
 
-    int sum = 0;
-    Iterator<Integer> it = queue.iterator();
-    while (it.hasNext()) {
-      int i = it.next();
-      if (i == 2) {
-        it.remove();
-      }
-      sum += i;
-    }
-    assertEquals(17, sum);
-    assertEquals(4, queue.size());
+  @Override
+  protected Object[] getOtherElements() {
+    return new Integer[] {5, 6, 7, 8};
+  }
 
-    try {
-      queue.iterator().remove();
-      fail();
-    } catch (IllegalStateException e) { }
+  @Override
+  protected Collection makeConfirmedCollection() {
+    return new ArrayList<>();
+  }
 
-    try {
-      Iterator<Integer> itt = queue.iterator();
-      while (itt.hasNext()) {
-        it.remove();
-        it.remove();
-        fail();
-      }
-    } catch (IllegalStateException e) { };
+  @Override
+  protected Collection makeConfirmedFullCollection() {
+    return new ArrayList<>(Arrays.asList(getFullElements()));
+  }
+
+  @Override
+  protected Collection makeCollection() {
+    return new PriorityQueue();
   }
 }