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 7fadc73..54eb4aa 100644
--- a/user/super/com/google/gwt/emul/java/util/PriorityQueue.java
+++ b/user/super/com/google/gwt/emul/java/util/PriorityQueue.java
@@ -15,6 +15,10 @@
  */
 package java.util;
 
+import static javaemul.internal.InternalPreconditions.checkArgument;
+import static javaemul.internal.InternalPreconditions.checkCriticalNotNull;
+import static javaemul.internal.InternalPreconditions.checkNotNull;
+
 /**
  * An unbounded priority queue based on a priority heap. <a
  * href="http://java.sun.com/j2se/1.5.0/docs/api/java/util/PriorityQueue.html">[Sun
@@ -86,6 +90,8 @@
 
   @Override
   public boolean addAll(Collection<? extends E> c) {
+    checkNotNull(c);
+    checkArgument(c != this);
     if (heap.addAll(c)) {
       makeHeap(0);
       return true;
@@ -104,7 +110,7 @@
 
   @Override
   public boolean contains(Object o) {
-    return heap.contains(o);
+    return indexOf(o) >= 0;
   }
 
   @Override
@@ -125,6 +131,7 @@
 
   @Override
   public boolean offer(E e) {
+    checkCriticalNotNull(e);
     int node = heap.size();
     heap.add(e);
     while (node > 0) {
@@ -162,7 +169,7 @@
 
   @Override
   public boolean remove(Object o) {
-    int index = heap.indexOf(o);
+    int index = indexOf(o);
     if (index < 0) {
       return false;
     }
@@ -268,6 +275,10 @@
     return smallestChild;
   }
 
+  private int indexOf(Object o) {
+    return o == null ? -1 : heap.indexOf(o);
+  }
+
   private boolean isLeaf(int node) {
     return isLeaf(node, heap.size());
   }
diff --git a/user/super/com/google/gwt/emul/java/util/Vector.java b/user/super/com/google/gwt/emul/java/util/Vector.java
index 01d0856..79f8f51 100644
--- a/user/super/com/google/gwt/emul/java/util/Vector.java
+++ b/user/super/com/google/gwt/emul/java/util/Vector.java
@@ -78,6 +78,7 @@
 
   @Override
   public boolean addAll(int index, Collection<? extends E> c) {
+    checkArrayElementIndex(index, size() + 1);
     return arrayList.addAll(index, c);
   }
 
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 5abe921..9342911 100644
--- a/user/test/com/google/gwt/emultest/java/util/PriorityQueueTest.java
+++ b/user/test/com/google/gwt/emultest/java/util/PriorityQueueTest.java
@@ -18,6 +18,7 @@
 import com.google.gwt.junit.client.GWTTestCase;
 
 import java.util.ArrayList;
+import java.util.Arrays;
 import java.util.Collection;
 import java.util.Comparator;
 import java.util.NoSuchElementException;
@@ -34,6 +35,40 @@
     return "com.google.gwt.emultest.EmulSuite";
   }
 
+  public void testAdd() {
+    PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
+
+    try {
+      queue.add(null);
+    } catch (NullPointerException expected) {
+    }
+
+    queue.add(1);
+    assertTrue(Arrays.asList(1).containsAll(queue));
+    queue.add(2);
+    assertTrue(Arrays.asList(1, 2).containsAll(queue));
+  }
+
+  public void testAddAll() {
+    PriorityQueue<Integer> queue = new PriorityQueue<>();
+    try {
+      queue.addAll(queue);
+      fail();
+    } catch (IllegalArgumentException expected) {
+    }
+
+    queue = new PriorityQueue<>();
+    try {
+      queue.addAll(Arrays.asList(1, null));
+      fail();
+    } catch (NullPointerException expected) {
+    }
+
+    queue = new PriorityQueue<>();
+    queue.addAll(Arrays.asList(2, 1, 3));
+    assertTrue(Arrays.asList(1, 2, 3).containsAll(queue));
+  }
+
   public void testBasic() {
     PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
     assertEquals(0, pq.size());
@@ -136,18 +171,69 @@
     assertEquals(13, pq.remove().intValue());
     assertTrue(pq.isEmpty());
   }
-  
-  public void testPollRemove() {
-    PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
-    try {
-      pq.remove();
-      fail("Expected NoSuchElementException");
-    } catch (NoSuchElementException e) {
-      // expected
-    }
-    assertNull(pq.poll());
+
+  public void testContains() {
+    PriorityQueue<Integer> queue = new PriorityQueue<>();
+
+    assertFalse(queue.contains(null));
+
+    queue.add(3);
+    queue.add(1);
+    queue.add(2);
+    assertTrue(queue.contains(1));
+    assertTrue(queue.contains(2));
+    assertTrue(queue.contains(3));
+    assertFalse(queue.contains(4));
   }
   
+  public void testPeekElement() {
+    PriorityQueue<Integer> queue = new PriorityQueue<>();
+    try {
+      queue.element();
+      fail();
+    } catch (NoSuchElementException expected) {
+    }
+    assertNull(queue.peek());
+
+    queue.add(3);
+    queue.add(1);
+    queue.add(2);
+    assertEquals(1, (int) queue.element());
+    assertEquals(1, (int) queue.peek());
+    assertEquals(3, queue.size());
+  }
+
+  public void testPollRemove() {
+    PriorityQueue<Integer> queue = new PriorityQueue<>();
+    try {
+      queue.remove();
+      fail();
+    } catch (NoSuchElementException expected) {
+    }
+    assertNull(queue.poll());
+
+    queue.add(3);
+    queue.add(1);
+    queue.add(2);
+    assertEquals(1, (int) queue.remove());
+    assertEquals(2, queue.size());
+    assertEquals(2, (int) queue.remove());
+    assertEquals(1, queue.size());
+    assertEquals(3, (int) queue.remove());
+    assertTrue(queue.isEmpty());
+
+    queue = new PriorityQueue<>();
+    queue.add(1);
+    queue.add(2);
+    queue.add(3);
+    assertEquals(1, (int) queue.poll());
+    assertEquals(2, queue.size());
+    assertEquals(2, (int) queue.poll());
+    assertEquals(1, queue.size());
+    assertEquals(3, (int) queue.poll());
+    assertTrue(queue.isEmpty());
+  }
+
   private void addArray(Collection<Integer> col, int... values) {
     for (int val : values) {
       col.add(val);