diff --git a/README.md b/README.md
index bb392fd..7ebd62a 100644
--- a/README.md
+++ b/README.md
@@ -8,14 +8,24 @@
 The `collection` package can be imported as separate libraries, or
 in totality:
 
-    import 'package:collection/equality.dart';
     import 'package:collection/algorithms.dart';
+    import 'package:collection/equality.dart';
+    import 'package:collection/iterable_zip.dart';
+    import 'package:collection/priority_queue.dart';
     import 'package:collection/wrappers.dart';
 
 or
 
     import 'package:collection/collection.dart';
 
+## Algorithms
+
+The algorithms library contains functions that operate on lists.
+
+It contains ways to shuffle a `List`, do binary search on a sorted `List`, and
+various sorting algorithms.
+
+
 ## Equality
 
 The equality library gives a way to specify equality of elements and
@@ -28,19 +38,23 @@
 case, for example, `const SetEquality(const IdentityEquality())` is an equality
 that considers two sets equal exactly if they contain identical elements.
 
-The library provides ways to define equalities on `Iterable`s, `List`s, `Set`s, and
-`Map`s, as well as combinations of these, such as:
+The library provides ways to define equalities on `Iterable`s, `List`s, `Set`s,
+and `Map`s, as well as combinations of these, such as:
 
     const MapEquality(const IdentityEquality(), const ListEquality());
 
-This equality considers maps equal if they have identical keys, and the corresponding values are lists with equal (`operator==`) values.
+This equality considers maps equal if they have identical keys, and the
+corresponding values are lists with equal (`operator==`) values.
 
-## Algorithms
 
-The algorithms library contains functions that operate on lists.
+## Iterable Zip
 
-It contains ways to shuffle a `List`, do binary search on a sorted `List`, and
-some different sorting algorithms.
+Utilities for "zipping" a list of iterables into an iterable of lists.
+
+
+## Priority Queue
+
+An interface and implemention of a priority queue.
 
 
 ## Wrappers
diff --git a/lib/collection.dart b/lib/collection.dart
index a6f192d..d640071 100644
--- a/lib/collection.dart
+++ b/lib/collection.dart
@@ -11,6 +11,7 @@
  *                      and various sorting algorithms).
  * - `equality.dart`: Different notions of equality of collections.
  * - `iterable_zip.dart`: Combining multiple iterables into one.
+ * - `priority_queue.dart`: Priority queue type and implementations.
  * - `wrappers.dart`: Wrapper classes that delegate to a collection object.
  *                    Includes unmodifiable views of collections.
  */
@@ -19,4 +20,5 @@
 export "algorithms.dart";
 export "equality.dart";
 export "iterable_zip.dart";
+export "priority_queue.dart";
 export "wrappers.dart";
diff --git a/lib/priority_queue.dart b/lib/priority_queue.dart
new file mode 100644
index 0000000..eb0cda3
--- /dev/null
+++ b/lib/priority_queue.dart
@@ -0,0 +1,383 @@
+// Copyright (c) 2014, the Dart project authors.  Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+library dart.pkg.collection.priority_queue;
+
+import "dart:collection" show SplayTreeSet;
+
+/**
+ * A priority queue is a priority based work-list of elements.
+ *
+ * The queue allows adding elements, and removing them again in priority order.
+ */
+abstract class PriorityQueue<E> {
+  /**
+   * Number of elements in the queue.
+   */
+  int get length;
+
+  /**
+   * Whether the queue is empty.
+   */
+  bool get isEmpty;
+
+  /**
+   * Whether the queue has any elements.
+   */
+  bool get isNotEmpty;
+
+  /**
+   * Checks if [object] is in the queue.
+   *
+   * Returns true if the element is found.
+   */
+  bool contains(E object);
+
+  /**
+   * Returns the next element that will be returned by [removeFirst].
+   *
+   * The element is not removed from the queue.
+   *
+   * The queue must not be empty when this method is called.
+   */
+  E get first;
+
+  /**
+   * Removes and returns the element with the highest priority.
+   *
+   * Repeatedly calling this method, without adding element in between,
+   * is guaranteed to return elements in non-decreasing order as, specified by
+   * [comparison].
+   *
+   * The queue must not be empty when this method is called.
+   */
+  E removeFirst();
+
+  /**
+   * Removes an element that compares equal to [element] in the queue.
+   *
+   * Returns true if an element is found and removed,
+   * and false if not equal element is found.
+   */
+  bool remove(E element);
+
+  /**
+   * Removes all the elements from this queue and returns them.
+   *
+   * The returned iterable has no specified order.
+   */
+  Iterable<E> removeAll();
+
+  /**
+   * Removes all the elements from this queue.
+   */
+  void clear();
+
+  /**
+   * Returns a list of the elements of this queue in priority order.
+   *
+   * The queue is not modified.
+   *
+   * The order is the order that the elements would be in if they were
+   * removed from this queue using [removeFirst].
+   */
+  List<E> toList();
+
+  /**
+   * Return a comparator based set using the comparator of this queue.
+   *
+   * The queue is not modified.
+   *
+   * The returned [Set] is currently a [SplayTreeSet],
+   * but this may change as other ordered sets are implemented.
+   *
+   * The set contains all the elements of this queue.
+   * If an element occurs more than once in the queue,
+   * the set will contain it only once.
+   */
+  Set<E> toSet();
+}
+
+/**
+ * Heap based priority queue.
+ *
+ * The elements are kept in a heap structure,
+ * where the element with the highest priority is immediately accessible,
+ * and modifying a single element takes
+ * logarithmic time in the number of elements on average.
+ *
+ * * The [add] and [removeFirst] operations take amortized logarithmic time,
+ *   O(log(n)), but may occasionally take linear time when growing the capacity
+ *   of the heap.
+ * * The [addAll] operation works as doing repeated [add] operations.
+ * * The [first] getter takes constant time, O(1).
+ * * The [clear] and [removeAll] methods also take constant time, O(1).
+ * * The [contains] and [remove] operations may need to search the entire
+ *   queue for the elements, taking O(n) time.
+ * * The [toList] operation effectively sorts the elements, taking O(n*log(n))
+ *   time.
+ * * The [toSet] operation effectively adds each element to the new set, taking
+ *   an expected O(n*log(n)) time.
+ */
+class HeapPriorityQueue<E> implements PriorityQueue<E> {
+  /**
+   * Initial capacity of a queue when created, or when added to after a [clear].
+   *
+   * Number can be any positive value. Picking a size that gives a whole
+   * number of "tree levels" in the heap is only done for aesthetic reasons.
+   */
+  static const int _INITIAL_CAPACITY = 7;
+
+  /**
+   * The comparison being used to compare the priority of elements.
+   */
+  final Comparator comparison;
+
+  /**
+   * List implementation of a heap.
+   */
+  List<E> _queue = new List<E>(_INITIAL_CAPACITY);
+
+  /**
+   * Number of elements in queue.
+   *
+   * The heap is implemented in the first [_length] entries of [_queue].
+   */
+  int _length = 0;
+
+  /**
+   * Create a new priority queue.
+   *
+   * The [comparison] is a [Comparator] used to compare the priority of
+   * elements. An element that compares as less than another element has
+   * a higher priority.
+   *
+   * If [comparison] is omitted, it defaults to [Comparable.compare].
+   */
+  HeapPriorityQueue([int comparison(E e1, E e2)])
+      : comparison = (comparison != null) ? comparison : Comparable.compare;
+
+  void add(E element) {
+    _add(element);
+  }
+
+  void addAll(Iterable<E> elements) {
+    for (E element in elements) {
+      _add(element);
+    }
+  }
+
+  void clear() {
+    _queue = const [];
+    _length = 0;
+  }
+
+  bool contains(E object) {
+    return _locate(object) >= 0;
+  }
+
+  E get first {
+    if (_length == 0) throw new StateError("No such element");
+    return _queue[0];
+  }
+
+  bool get isEmpty => _length == 0;
+
+  bool get isNotEmpty => _length != 0;
+
+  int get length => _length;
+
+  bool remove(E element) {
+    int index = _locate(element);
+    if (index < 0) return false;
+    E last = _removeLast();
+    if (index < _length) {
+      int comp = comparison(last, element);
+      if (comp <= 0) {
+        _bubbleUp(last, index);
+      } else {
+        _bubbleDown(last, index);
+      }
+    }
+    return true;
+  }
+
+  Iterable<E> removeAll() {
+    List<E> result = _queue;
+    int length = _length;
+    _queue = const [];
+    _length = 0;
+    return result.take(length);
+  }
+
+  E removeFirst() {
+    if (_length == 0) throw new StateError("No such element");
+    E result = _queue[0];
+    E last = _removeLast();
+    if (_length > 0) {
+      _bubbleDown(last, 0);
+    }
+    return result;
+  }
+
+  List<E> toList() {
+    List<E> list = new List<E>()..length = _length;
+    list.setRange(0, _length, _queue);
+    list.sort(comparison);
+    return list;
+  }
+
+  Set<E> toSet() {
+    Set<E> set = new SplayTreeSet<E>(comparison);
+    for (int i = 0; i < _length; i++) {
+      set.add(_queue[i]);
+    }
+    return set;
+  }
+
+  /**
+   * Returns some representation of the queue.
+   *
+   * The format isn't significant, and may change in the future.
+   */
+  String toString() {
+    return _queue.take(_length).toString();
+  }
+
+  /**
+   * Add element to the queue.
+   *
+   * Grows the capacity if the backing list is full.
+   */
+  void _add(E element) {
+    if (_length == _queue.length) _grow();
+    _bubbleUp(element, _length++);
+  }
+
+  /**
+   * Find the index of an object in the heap.
+   *
+   * Returns -1 if the object is not found.
+   */
+  int _locate(E object) {
+    if (_length == 0) return -1;
+    // Count positions from one instad of zero. This gives the numbers
+    // some nice properties. For example, all right children are odd,
+    // their left sibling is even, and the parent is found by shifting
+    // right by one.
+    // Valid range for position is [1.._length], inclusive.
+    int position = 1;
+    // Pre-order depth first search, omit child nodes if the current
+    // node has lower priority than [object], because all nodes lower
+    // in the heap will also have lower priority.
+    do {
+      int index = position - 1;
+      E element = _queue[index];
+      int comp = comparison(element, object);
+      if (comp == 0) return index;
+      if (comp < 0) {
+        // Element may be in subtree.
+        // Continue with the left child, if it is there.
+        int leftChildPosition = position * 2;
+        if (leftChildPosition <= _length) {
+          position = leftChildPosition;
+          continue;
+        }
+      }
+      // Find the next right sibling or right ancestor sibling.
+      do {
+        while (position.isOdd) {
+          // While position is a right child, go to the parent.
+          position >>= 1;
+        }
+        // Then go to the right sibling of the left-child.
+        position += 1;
+      } while (position > _length);  // Happens if last element is a left child.
+    } while (position != 1);  // At root again. Happens for right-most element.
+    return -1;
+  }
+
+  E _removeLast() {
+    int newLength = _length - 1;
+    E last = _queue[newLength];
+    _queue[newLength] = null;
+    _length = newLength;
+    return last;
+  }
+
+  /**
+   * Place [element] in heap at [index] or above.
+   *
+   * Put element into the empty cell at `index`.
+   * While the `element` has higher priority than the
+   * parent, swap it with the parent.
+   */
+  void _bubbleUp(E element, int index) {
+    while (index > 0) {
+      int parentIndex = (index - 1) ~/ 2;
+      E parent = _queue[parentIndex];
+      if (comparison(element, parent) > 0) break;
+      _queue[index] = parent;
+      index = parentIndex;
+    }
+    _queue[index] = element;
+  }
+
+  /**
+   * Place [element] in heap at [index] or above.
+   *
+   * Put element into the empty cell at `index`.
+   * While the `element` has lower priority than either child,
+   * swap it with the highest priority child.
+   */
+  void _bubbleDown(E element, int index) {
+    int rightChildIndex = index * 2 + 2;
+    while (rightChildIndex < _length) {
+      int leftChildIndex = rightChildIndex - 1;
+      E leftChild = _queue[leftChildIndex];
+      E rightChild = _queue[rightChildIndex];
+      int comp = comparison(leftChild, rightChild);
+      int minChildIndex;
+      E minChild;
+      if (comp < 0) {
+        minChild = leftChild;
+        minChildIndex = leftChildIndex;
+      } else {
+        minChild = rightChild;
+        minChildIndex = rightChildIndex;
+      }
+      comp = comparison(element, minChild);
+      if (comp <= 0) {
+        _queue[index] = element;
+        return;
+      }
+      _queue[index] = minChild;
+      index = minChildIndex;
+      rightChildIndex = index * 2 + 2;
+    }
+    int leftChildIndex = rightChildIndex - 1;
+    if (leftChildIndex < _length) {
+      E child = _queue[leftChildIndex];
+      int comp = comparison(element, child);
+      if (comp > 0) {
+        _queue[index] = child;
+        index = leftChildIndex;
+      }
+    }
+    _queue[index] = element;
+  }
+
+  /**
+   * Grows the capacity of the list holding the heap.
+   *
+   * Called when the list is full.
+   */
+  void _grow() {
+    int newCapacity = _queue.length * 2 + 1;
+    if (newCapacity < _INITIAL_CAPACITY) newCapacity = _INITIAL_CAPACITY;
+    List<E> newQueue = new List<E>(newCapacity);
+    newQueue.setRange(0, _length, _queue);
+    _queue = newQueue;
+  }
+}
diff --git a/pubspec.yaml b/pubspec.yaml
index 0fec04b..09c07a7 100644
--- a/pubspec.yaml
+++ b/pubspec.yaml
@@ -1,5 +1,5 @@
 name: collection
-version: 0.9.0
+version: 0.9.1-dev
 author: Dart Team <misc@dartlang.org>
 description: Collections and utilities functions and classes related to collections.
 homepage: http://www.dartlang.org
diff --git a/test/priority_queue_test.dart b/test/priority_queue_test.dart
new file mode 100644
index 0000000..3d9c9fd
--- /dev/null
+++ b/test/priority_queue_test.dart
@@ -0,0 +1,167 @@
+// Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+/// Tests priority queue implementations utilities.
+
+import "dart:collection";
+import "package:collection/priority_queue.dart";
+import "package:unittest/unittest.dart";
+
+void main() {
+  testInt(() => new HeapPriorityQueue<int>());
+  testCustom((comparator) => new HeapPriorityQueue<C>(comparator));
+}
+
+void testInt(PriorityQueue<int> create()) {
+  for (int count in [1, 5, 127, 128, 400]) {
+    testQueue("int:$count",
+              create,
+              new List<int>.generate(count, (x) => x),
+              count);
+  }
+}
+
+void testCustom(PriorityQueue<C> create(comparator)) {
+  for (int count in [1, 5, 127, 128, 400]) {
+    testQueue("Custom:$count/null",
+              () => create(null),
+              new List<C>.generate(count, (x) => new C(x)),
+              new C(count));
+    testQueue("Custom:$count/compare",
+              () => create(compare),
+              new List<C>.generate(count, (x) => new C(x)),
+              new C(count));
+    testQueue("Custom:$count/compareNeg",
+              () => create(compareNeg),
+              new List<C>.generate(count, (x) => new C(count - x)),
+              new C(0));
+  }
+}
+
+/**
+ * Test that a queue behaves correctly.
+ *
+ * The elements must be in priority order, from highest to lowest.
+ */
+void testQueue(String name, PriorityQueue create(), List elements, notElement) {
+  test(name, () => testQueueBody(create, elements, notElement));
+}
+
+void testQueueBody(PriorityQueue create(), List elements, notElement) {
+  PriorityQueue q = create();
+  expect(q.isEmpty, isTrue);
+  expect(q, hasLength(0));
+  expect(() { q.first; }, throwsStateError);
+  expect(() { q.removeFirst(); }, throwsStateError);
+
+  // Tests removeFirst, first, contains, toList and toSet.
+  void testElements() {
+    expect(q.isNotEmpty, isTrue);
+    expect(q, hasLength(elements.length));
+
+    expect(q.toList(), equals(elements));
+    expect(q.toSet().toList(), equals(elements));
+
+    for (int i = 0; i < elements.length; i++) {
+      expect(q.contains(elements[i]), isTrue);
+    }
+    expect(q.contains(notElement), isFalse);
+
+    List all = [];
+    while (!q.isEmpty) {
+      var expected = q.first;
+      var actual = q.removeFirst();
+      expect(actual, same(expected));
+      all.add(actual);
+    }
+
+    expect(all.length, elements.length);
+    for (int i = 0; i < all.length; i++) {
+      expect(all[i], same(elements[i]));
+    }
+
+    expect(q.isEmpty, isTrue);
+  }
+
+  q.addAll(elements);
+  testElements();
+
+  q.addAll(elements.reversed);
+  testElements();
+
+  // Add elements in a non-linear order (gray order).
+  for (int i = 0, j = 0; i < elements.length; i++) {
+    int gray;
+    do {
+      gray = j ^ (j >> 1);
+      j++;
+    } while (gray >= elements.length);
+    q.add(elements[gray]);
+  }
+  testElements();
+
+  // Add elements by picking the middle element first, and then recursing
+  // on each side.
+  void addRec(int min, int max) {
+    int mid = min + ((max - min) >> 1);
+    q.add(elements[mid]);
+    if (mid + 1 < max) addRec(mid + 1, max);
+    if (mid > min) addRec(min, mid);
+  }
+  addRec(0, elements.length);
+  testElements();
+
+  // Test removeAll.
+  q.addAll(elements);
+  expect(q, hasLength(elements.length));
+  Iterable all = q.removeAll();
+  expect(q.isEmpty, isTrue);
+  expect(all, hasLength(elements.length));
+  for (int i = 0; i < elements.length; i++) {
+    expect(all, contains(elements[i]));
+  }
+
+  // Test the same element more than once in queue.
+  q.addAll(elements);
+  q.addAll(elements.reversed);
+  expect(q, hasLength(elements.length * 2));
+  for (int i = 0; i < elements.length; i++) {
+    var element = elements[i];
+    expect(q.contains(element), isTrue);
+    expect(q.removeFirst(), element);
+    expect(q.removeFirst(), element);
+  }
+
+  // Test queue with all same element.
+  var a = elements[0];
+  for (int i = 0; i < elements.length; i++) {
+    q.add(a);
+  }
+  expect(q, hasLength(elements.length));
+  expect(q.contains(a), isTrue);
+  expect(q.contains(notElement), isFalse);
+  q.removeAll().forEach((x) => expect(x, same(a)));
+
+  // Test remove.
+  q.addAll(elements);
+  for (var element in elements.reversed) {
+    expect(q.remove(element), isTrue);
+  }
+  expect(q.isEmpty, isTrue);
+}
+
+
+// Custom class.
+// Class is comparable, comparators match normal and inverse order.
+int compare(C c1, C c2) => c1.value - c2.value;
+int compareNeg(C c1, C c2) => c2.value - c1.value;
+
+class C implements Comparable {
+  final int value;
+  const C(this.value);
+  int get hashCode => value;
+  bool operator==(Object other) => other is C && value == other.value;
+  int compareTo(C other) => value - other.value;
+  String toString() => "C($value)";
+}