--- a/xpcom/glue/nsTArray.h
+++ b/xpcom/glue/nsTArray.h
@@ -872,30 +872,101 @@ class nsTArray : public nsTArray_base {
     }
 
     //
     // Sorting
     //
 
     // This method sorts the elements of the array.  It uses the LessThan
     // method defined on the given Comparator object to collate elements.
-    // @param c  The Comparator to used to collate elements.
+    // @param comp The Comparator used to collate elements.
     template<class Comparator>
     void Sort(const Comparator& comp) {
       NS_QuickSort(Elements(), Length(), sizeof(elem_type),
                    nsQuickSortComparator<elem_type, Comparator>::Compare,
                    const_cast<Comparator*>(&comp));
     }
 
     // A variation on the Sort method defined above that assumes that
     // 'operator<' is defined for elem_type.
     void Sort() {
       Sort(nsDefaultComparator<elem_type, elem_type>());
     }
 
+    //
+    // Binary Heap
+    //
+
+    // Sorts the array into a binary heap.
+    // @param comp The Comparator used to create the heap
+    template<class Comparator>
+    void MakeHeap(const Comparator& comp) {
+      if (!Length()) {
+        return;
+      }
+      elem_type *elem = Elements();
+      index_type index = (Length() - 1) / 2;
+      do {
+        SiftDown(index, comp);
+      } while (index--);
+    }
+
+    // A variation on the MakeHeap method defined above.
+    void MakeHeap() {
+      MakeHeap(nsDefaultComparator<elem_type, elem_type>());
+    }
+
+    // Adds an element to the heap
+    // @param item The item to add
+    // @param comp The Comparator used to sift-up the item
+    template<class Item, class Comparator>
+    elem_type *PushHeap(const Item& item, const Comparator& comp) {
+      if (!nsTArray_base::InsertSlotsAt(Length(), 1, sizeof(elem_type))) {
+        return nsnull;
+      }
+      // Sift up the new node
+      elem_type *elem = Elements();
+      index_type index = Length() - 1;
+      index_type parent_index = (index - 1) / 2;
+      while (index && comp.LessThan(elem[parent_index], item)) {
+        elem[index] = elem[parent_index];
+        index = parent_index;
+        parent_index = (index - 1) / 2;
+      }
+      elem[index] = item;
+      return &elem[index];
+    }
+
+    // A variation on the PushHeap method defined above.
+    template<class Item>
+    elem_type *PushHeap(const Item& item) {
+      return PushHeap(item, nsDefaultComparator<elem_type, Item>());
+    }
+
+    // Delete the root of the heap and restore the heap
+    // @param comp The Comparator used to restore the heap
+    template<class Comparator>
+    void PopHeap(const Comparator& comp) {
+      if (!Length()) {
+        return;
+      }
+      index_type last_index = Length() - 1;
+      elem_type *elem = Elements();
+      elem[0] = elem[last_index];
+      TruncateLength(last_index);
+      if (Length()) {
+        SiftDown(0, comp);
+      }
+    }
+
+    // A variation on the PopHeap method defined above.
+    void PopHeap() {
+      PopHeap(nsDefaultComparator<elem_type, elem_type>());
+    }
+
   protected:
 
     // This method invokes elem_type's destructor on a range of elements.
     // @param start  The index of the first element to destroy.
     // @param count  The number of elements to destroy.
     void DestructRange(index_type start, size_type count) {
       elem_type *iter = Elements() + start, *end = iter + count;
       for (; iter != end; ++iter) {
@@ -910,16 +981,46 @@ class nsTArray : public nsTArray_base {
     template<class Item>
     void AssignRange(index_type start, size_type count,
                      const Item *values) {
       elem_type *iter = Elements() + start, *end = iter + count;
       for (; iter != end; ++iter, ++values) {
         elem_traits::Construct(iter, *values);
       }
     }
+
+    // This method sifts an item down to its proper place in a binary heap
+    // @param index The index of the node to start sifting down from
+    // @param comp  The Comparator used to sift down
+    template<class Comparator>
+    void SiftDown(index_type index, const Comparator& comp) {
+      elem_type *elem = Elements();
+      elem_type item = elem[index];
+      index_type end = Length() - 1;
+      while ((index * 2) < end) {
+        const index_type left = (index * 2) + 1;
+        const index_type right = (index * 2) + 2;
+        const index_type parent_index = index;
+        if (comp.LessThan(item, elem[left])) {
+          if (left < end &&
+              comp.LessThan(elem[left], elem[right])) {
+            index = right;
+          } else {
+            index = left;
+          }
+        } else if (left < end &&
+                   comp.LessThan(item, elem[right])) {
+          index = right;
+        } else {
+          break;
+        }
+        elem[parent_index] = elem[index];
+      }
+      elem[index] = item;
+    }
 };
 
 template<class E, PRUint32 N>
 class nsAutoTArray : public nsTArray<E> {
   public:
     typedef nsTArray<E> base_type;
     typedef typename base_type::Header Header;
     typedef typename base_type::elem_type elem_type;

--- a/xpcom/tests/TestTArray.cpp
+++ b/xpcom/tests/TestTArray.cpp
@@ -518,16 +518,55 @@ static PRBool test_indexof() {
   array.AppendElement(5);
   array.RemoveElementAt(1);
   // we should not find the 5!
   return array.IndexOf(5, 1) == array.NoIndex;
 }
 
 //----
 
+template <class Array>
+static PRBool is_heap(const Array& ary, PRUint32 len) {
+  PRUint32 index = 1;
+  while (index < len) {
+    if (ary[index] > ary[(index - 1) >> 1])
+      return PR_FALSE;
+    index++;
+  }
+  return PR_TRUE;
+} 
+
+static PRBool test_heap() {
+  const int data[] = {4,6,8,2,4,1,5,7,3};
+  nsTArray<int> ary;
+  ary.AppendElements(data, NS_ARRAY_LENGTH(data));
+  // make a heap and make sure it's a heap
+  ary.MakeHeap();
+  if (!is_heap(ary, NS_ARRAY_LENGTH(data)))
+    return PR_FALSE;
+  // pop the root and make sure it's still a heap
+  int root = ary[0];
+  ary.PopHeap();
+  if (!is_heap(ary, NS_ARRAY_LENGTH(data) - 1))
+    return PR_FALSE;
+  // push the previously poped value back on and make sure it's still a heap
+  ary.PushHeap(root);
+  if (!is_heap(ary, NS_ARRAY_LENGTH(data)))
+    return PR_FALSE;
+  // make sure the heap looks like what we expect
+  const int expected_data[] = {8,7,5,6,4,1,4,2,3};
+  PRUint32 index;
+  for (index = 0; index < NS_ARRAY_LENGTH(data); index++)
+    if (ary[index] != expected_data[index])
+      return PR_FALSE;
+  return PR_TRUE;
+}
+
+//----
+
 typedef PRBool (*TestFunc)();
 #define DECL_TEST(name) { #name, name }
 
 static const struct Test {
   const char* name;
   TestFunc    func;
 } tests[] = {
   DECL_TEST(test_int_array),
@@ -538,16 +577,17 @@ static const struct Test {
   DECL_TEST(test_string_array),
   DECL_TEST(test_comptr_array),
   DECL_TEST(test_refptr_array),
   DECL_TEST(test_ptrarray),
 #ifdef DEBUG
   DECL_TEST(test_autoarray),
 #endif
   DECL_TEST(test_indexof),
+  DECL_TEST(test_heap),
   { nsnull, nsnull }
 };
 
 }
 
 using namespace TestTArray;
 
 int main(int argc, char **argv) {