diff --git a/glib/Makefile.am b/glib/Makefile.am
index d9892f6..f8c9dd1 100644
--- a/glib/Makefile.am
+++ b/glib/Makefile.am
@@ -127,6 +127,7 @@
 	gfileutils.c		\
 	ggettext.c		\
 	ghash.c			\
+	gheap.c			\
 	ghmac.c			\
 	ghook.c			\
 	ghostutils.c		\
@@ -263,6 +264,7 @@
 	gfileutils.h	\
 	ggettext.h	\
 	ghash.h		\
+	gheap.h		\
 	ghmac.h		\
 	ghook.h		\
 	ghostutils.h	\
diff --git a/glib/gheap.c b/glib/gheap.c
new file mode 100644
index 0000000..852dd44
--- /dev/null
+++ b/glib/gheap.c
@@ -0,0 +1,364 @@
+/* gheap.c
+ *
+ * Copyright (C) 2014 Christian Hergert <christian@hergert.me>
+ *
+ * This file is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This file is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "config.h"
+
+#include <string.h>
+
+#include "gheap.h"
+
+/**
+ * SECTION:gheap
+ * @title: Heaps
+ * @short_description: efficient priority queues using min/max heaps
+ *
+ * Heaps are similar to a partially sorted tree but implemented as an
+ * array. They allow for efficient O(1) lookup of the highest priority
+ * item as it will always be the first item of the array.
+ *
+ * To create a new heap use g_heap_new().
+ *
+ * To add items to the heap, use g_heap_insert_val() or
+ * g_heap_insert_vals() to insert in bulk.
+ *
+ * To access an item in the heap, use g_heap_index().
+ *
+ * To remove an arbitrary item from the heap, use g_heap_extract_index().
+ *
+ * To remove the highest priority item in the heap, use g_heap_extract().
+ *
+ * To free a heap, use g_heap_unref().
+ *
+ * Here is an example that stores integers in a #GHeap:
+ * |[<!-- language="C" -->
+ * static int
+ * cmpint (gconstpointer a,
+ *         gconstpointer b)
+ * {
+ *   return *(const gint *)a - *(const gint *)b;
+ * }
+ *
+ * int
+ * main (gint   argc,
+ *       gchar *argv[])
+ * {
+ *   GHeap *heap;
+ *   gint i;
+ *   gint v;
+ *
+ *   heap = g_heap_new (sizeof (gint), cmpint);
+ *
+ *   for (i = 0; i < 10000; i++)
+ *     g_heap_insert_val (heap, i);
+ *   for (i = 0; i < 10000; i++)
+ *     g_heap_extract (heap, &v);
+ *
+ *   g_heap_unref (heap);
+ * }
+ * ]|
+ */
+
+#define MIN_HEAP_SIZE 16
+
+/*
+ * Based upon Mastering Algorithms in C by Kyle Loudon.
+ * Section 10 - Heaps and Priority Queues.
+ */
+
+typedef struct _GHeapReal GHeapReal;
+
+struct _GHeapReal
+{
+    gchar          *data;
+    gsize           len;
+    volatile gint   ref_count;
+    guint           element_size;
+    gsize           allocated_len;
+    GCompareFunc    compare;
+    gchar           tmp[0];
+};
+
+#define heap_parent(npos)   (((npos)-1)/2)
+#define heap_left(npos)     (((npos)*2)+1)
+#define heap_right(npos)    (((npos)*2)+2)
+#define heap_index(h,i)     ((h)->data + (i * (h)->element_size))
+#define heap_compare(h,a,b) ((h)->compare(heap_index(h,a), heap_index(h,b)))
+#define heap_swap(h,a,b) \
+    G_STMT_START { \
+        memcpy ((h)->tmp, heap_index (h, a), (h)->element_size); \
+        memcpy (heap_index (h, a), heap_index (h, b), (h)->element_size); \
+        memcpy (heap_index (h, b), (h)->tmp, (h)->element_size); \
+   } G_STMT_END
+
+GHeap *
+g_heap_new (guint          element_size,
+            GCompareFunc   compare_func)
+{
+    GHeapReal *real;
+
+    g_return_val_if_fail (element_size, NULL);
+    g_return_val_if_fail (compare_func, NULL);
+
+    real = g_malloc_n (1, sizeof (GHeapReal) + element_size);
+    real->data = NULL;
+    real->len = 0;
+    real->ref_count = 1;
+    real->element_size = element_size;
+    real->allocated_len = 0;
+    real->compare = compare_func;
+
+    return (GHeap *)real;
+}
+
+GHeap *
+g_heap_ref (GHeap *heap)
+{
+    GHeapReal *real = (GHeapReal *)heap;
+
+    g_return_val_if_fail (heap, NULL);
+    g_return_val_if_fail (real->ref_count, NULL);
+
+    g_atomic_int_inc (&real->ref_count);
+
+    return heap;
+}
+
+static void
+g_heap_real_free (GHeapReal *real)
+{
+    g_assert (real);
+    g_assert_cmpint (real->ref_count, ==, 0);
+
+    g_free (real->data);
+    g_free (real);
+}
+
+void
+g_heap_unref (GHeap *heap)
+{
+    GHeapReal *real = (GHeapReal *)heap;
+
+    g_return_if_fail (heap);
+    g_return_if_fail (real->ref_count);
+
+    if (g_atomic_int_dec_and_test (&real->ref_count)) {
+        g_heap_real_free (real);
+    }
+}
+
+static void
+g_heap_real_grow (GHeapReal *real)
+{
+    g_assert (real);
+    g_assert_cmpint (real->allocated_len, <, G_MAXSIZE / 2);
+
+    real->allocated_len = MAX (MIN_HEAP_SIZE, (real->allocated_len * 2));
+    real->data = g_realloc_n (real->data,
+                              real->allocated_len,
+                              real->element_size);
+}
+
+static void
+g_heap_real_shrink (GHeapReal *real)
+{
+   g_assert (real);
+   g_assert ((real->allocated_len / 2) >= real->len);
+
+   real->allocated_len = MAX (MIN_HEAP_SIZE, real->allocated_len / 2);
+   real->data = g_realloc_n (real->data,
+                             real->allocated_len,
+                             real->element_size);
+}
+
+static void
+g_heap_real_insert_val (GHeapReal     *real,
+                        gconstpointer  data)
+{
+    gint ipos;
+    gint ppos;
+
+    g_assert (real);
+    g_assert (data);
+
+    if (G_UNLIKELY (real->len == real->allocated_len)) {
+        g_heap_real_grow (real);
+    }
+
+    memcpy (real->data + (real->element_size * real->len), data,
+            real->element_size);
+
+    ipos = real->len;
+    ppos = heap_parent (ipos);
+
+    while ((ipos > 0) && (heap_compare (real, ppos, ipos) < 0)) {
+        heap_swap (real, ppos, ipos);
+        ipos = ppos;
+        ppos = heap_parent (ipos);
+    }
+
+    real->len++;
+}
+
+void
+g_heap_insert_vals (GHeap         *heap,
+                    gconstpointer  data,
+                    guint          len)
+{
+    GHeapReal *real = (GHeapReal *)heap;
+    const gchar *ptr = data;
+    guint i;
+
+    g_return_if_fail (heap);
+    g_return_if_fail (data);
+    g_return_if_fail (len);
+
+    for (i = 0; i < len; i++, ptr += real->element_size) {
+        g_heap_real_insert_val (real, ptr);
+    }
+}
+
+gboolean
+g_heap_extract (GHeap    *heap,
+                gpointer  result)
+{
+    GHeapReal *real = (GHeapReal *)heap;
+    gboolean ret;
+    gint ipos;
+    gint lpos;
+    gint rpos;
+    gint mpos;
+
+    g_return_val_if_fail (heap, FALSE);
+
+    ret = (real->len > 0);
+
+    if (ret) {
+       if (result) {
+          memcpy (result, heap_index (real, 0), real->element_size);
+       }
+
+       if (real->len && --real->len) {
+           memmove (real->data, heap_index (real, real->len), real->element_size);
+
+           ipos = 0;
+
+           for (;;) {
+               lpos = heap_left (ipos);
+               rpos = heap_right (ipos);
+
+               if ((lpos < real->len) && (heap_compare (real, lpos, ipos) > 0)) {
+                   mpos = lpos;
+               } else {
+                   mpos = ipos;
+               }
+
+               if ((rpos < real->len) && (heap_compare (real, rpos, mpos) > 0)) {
+                   mpos = rpos;
+               }
+
+               if (mpos == ipos) {
+                   break;
+               }
+
+               heap_swap (real, mpos, ipos);
+
+               ipos = mpos;
+           }
+       }
+    }
+
+    if ((real->len >= MIN_HEAP_SIZE) &&
+        (real->allocated_len / 2) >= real->len) {
+       g_heap_real_shrink (real);
+    }
+
+    return ret;
+}
+
+gboolean
+g_heap_extract_index (GHeap    *heap,
+                      guint     index_,
+                      gpointer  result)
+{
+    GHeapReal *real = (GHeapReal *)heap;
+    gboolean ret;
+    gint ipos;
+    gint lpos;
+    gint mpos;
+    gint ppos;
+    gint rpos;
+
+    g_return_val_if_fail (heap, FALSE);
+
+    ret = (real->len > 0);
+
+    if (real->len) {
+       if (result) {
+          memcpy (result, heap_index (real, 0), real->element_size);
+       }
+
+       real->len--;
+
+       if (real->len && index_ != real->len) {
+           memcpy (heap_index (real, index_),
+                   heap_index (real, real->len),
+                   real->element_size);
+
+           ipos = index_;
+           ppos = heap_parent (ipos);
+
+           while (heap_compare (real, ipos, ppos) > 0) {
+               heap_swap (real, ipos, ppos);
+               ipos = ppos;
+               ppos = heap_parent (ppos);
+           }
+
+           if (ipos == index_) {
+               for (;;) {
+                   lpos = heap_left (ipos);
+                   rpos = heap_right (ipos);
+
+                   if ((lpos < real->len) && (heap_compare (real, lpos, ipos) > 0)) {
+                       mpos = lpos;
+                   } else {
+                       mpos = ipos;
+                   }
+
+                   if ((rpos < real->len) && (heap_compare (real, rpos, mpos) > 0)) {
+                       mpos = rpos;
+                   }
+
+                   if (mpos == ipos) {
+                       break;
+                   }
+
+                   heap_swap (real, mpos, ipos);
+
+                   ipos = mpos;
+               }
+           }
+       }
+    }
+
+    if ((real->len >= MIN_HEAP_SIZE) &&
+        (real->allocated_len / 2) >= real->len) {
+       g_heap_real_shrink (real);
+    }
+
+    return ret;
+}
diff --git a/glib/gheap.h b/glib/gheap.h
new file mode 100644
index 0000000..b964d68
--- /dev/null
+++ b/glib/gheap.h
@@ -0,0 +1,59 @@
+/* gheap.h
+ *
+ * Copyright (C) 2014 Christian Hergert <christian@hergert.me>
+ *
+ * This file is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This file is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef G_HEAP_H
+#define G_HEAP_H
+
+#include <glib.h>
+
+G_BEGIN_DECLS
+
+#define g_heap_insert_val(h,v) g_heap_insert_vals(h,&(v),1)
+#define g_heap_index(h,t,i)    (((t*)(h)->data)[i])
+#define g_heap_peek(h,t)       g_heap_index(h,t,0)
+
+typedef struct _GHeap GHeap;
+
+struct _GHeap
+{
+   gchar *data;
+   guint  len;
+};
+
+GLIB_AVAILABLE_IN_2_42
+GHeap   *g_heap_new           (guint           element_size,
+                               GCompareFunc    compare_func);
+GLIB_AVAILABLE_IN_2_42
+GHeap   *g_heap_ref           (GHeap          *heap);
+GLIB_AVAILABLE_IN_2_42
+void     g_heap_unref         (GHeap          *heap);
+GLIB_AVAILABLE_IN_2_42
+void     g_heap_insert_vals   (GHeap          *heap,
+                               gconstpointer   data,
+                               guint           len);
+GLIB_AVAILABLE_IN_2_42
+gboolean g_heap_extract       (GHeap          *heap,
+                               gpointer        result);
+GLIB_AVAILABLE_IN_2_42
+gboolean g_heap_extract_index (GHeap          *heap,
+                               guint           index_,
+                               gpointer        result);
+
+G_END_DECLS
+
+#endif /* G_HEAP_H */
diff --git a/glib/glib.h b/glib/glib.h
index c7fc999..a5d5eb6 100644
--- a/glib/glib.h
+++ b/glib/glib.h
@@ -48,6 +48,7 @@
 #include <glib/gfileutils.h>
 #include <glib/ggettext.h>
 #include <glib/ghash.h>
+#include <glib/gheap.h>
 #include <glib/ghmac.h>
 #include <glib/ghook.h>
 #include <glib/ghostutils.h>
diff --git a/glib/tests/.gitignore b/glib/tests/.gitignore
index 33ef15e..20ca63c 100644
--- a/glib/tests/.gitignore
+++ b/glib/tests/.gitignore
@@ -25,6 +25,7 @@
 gwakeup
 gwakeup-fallback
 hash
+gheap
 hmac
 hook
 hostutils
diff --git a/glib/tests/Makefile.am b/glib/tests/Makefile.am
index 445040a..2311d34 100644
--- a/glib/tests/Makefile.am
+++ b/glib/tests/Makefile.am
@@ -48,6 +48,7 @@
 	error				\
 	fileutils			\
 	gdatetime			\
+	gheap				\
 	gvariant			\
 	hash				\
 	hmac				\
diff --git a/glib/tests/gheap.c b/glib/tests/gheap.c
new file mode 100644
index 0000000..9b48339
--- /dev/null
+++ b/glib/tests/gheap.c
@@ -0,0 +1,176 @@
+/* gheap.c
+ *
+ * Copyright (C) 2014 Christian Hergert <christian@hergert.me>
+ *
+ * This file is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This file is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "config.h"
+
+#include <glib.h>
+
+typedef struct
+{
+   gint64 size;
+   gpointer pointer;
+} Tuple;
+
+static int
+cmpint_rev (gconstpointer a,
+            gconstpointer b)
+{
+   return *(const gint *)b - *(const gint *)a;
+}
+
+static int
+cmpptr_rev (gconstpointer a,
+            gconstpointer b)
+{
+   return GPOINTER_TO_SIZE(*(gpointer *)b) - GPOINTER_TO_SIZE (*(gpointer *)a);
+}
+
+static int
+cmptuple_rev (gconstpointer a,
+              gconstpointer b)
+{
+   Tuple *at = (Tuple *)a;
+   Tuple *bt = (Tuple *)b;
+
+   return bt->size - at->size;
+}
+
+static void
+test_GHeap_insert_val_int (void)
+{
+   GHeap *heap;
+   gint i;
+
+   heap = g_heap_new (sizeof (gint), cmpint_rev);
+
+   for (i = 0; i < 100000; i++) {
+      g_heap_insert_val (heap, i);
+      g_assert_cmpint (heap->len, ==, i + 1);
+   }
+
+   for (i = 0; i < 100000; i++) {
+      g_assert_cmpint (heap->len, ==, 100000 - i);
+      g_assert_cmpint (g_heap_peek (heap, gint), ==, i);
+      g_heap_extract (heap, NULL);
+   }
+
+   g_heap_unref (heap);
+}
+
+static void
+test_GHeap_insert_val_ptr (void)
+{
+   gconstpointer ptr;
+   GHeap *heap;
+   gint i;
+
+   heap = g_heap_new (sizeof (gpointer), cmpptr_rev);
+
+   for (i = 0; i < 100000; i++) {
+      ptr = GINT_TO_POINTER (i);
+      g_heap_insert_val (heap, ptr);
+      g_assert_cmpint (heap->len, ==, i + 1);
+   }
+
+   for (i = 0; i < 100000; i++) {
+      g_assert_cmpint (heap->len, ==, 100000 - i);
+      g_assert (g_heap_peek (heap, gpointer) == GINT_TO_POINTER (i));
+      g_heap_extract (heap, NULL);
+   }
+
+   g_heap_unref (heap);
+}
+
+static void
+test_GHeap_insert_val_tuple (void)
+{
+   Tuple t;
+   GHeap *heap;
+   gint i;
+
+   heap = g_heap_new (sizeof (Tuple), cmptuple_rev);
+
+   for (i = 0; i < 100000; i++) {
+      t.pointer = GINT_TO_POINTER (i);
+      t.size = i;
+      g_heap_insert_val (heap, t);
+      g_assert_cmpint (heap->len, ==, i + 1);
+   }
+
+   for (i = 0; i < 100000; i++) {
+      g_assert_cmpint (heap->len, ==, 100000 - i);
+      g_assert (g_heap_peek (heap, Tuple).size == i);
+      g_assert (g_heap_peek (heap, Tuple).pointer == GINT_TO_POINTER (i));
+      g_heap_extract (heap, NULL);
+   }
+
+   g_heap_unref (heap);
+}
+
+static void
+test_GHeap_extract_int (void)
+{
+   GHeap *heap;
+   gint removed[5];
+   gint i;
+   gint v;
+
+   heap = g_heap_new (sizeof (gint), cmpint_rev);
+
+   for (i = 0; i < 100000; i++) {
+      g_heap_insert_val (heap, i);
+   }
+
+   removed [0] = g_heap_index (heap, gint, 1578); g_heap_extract_index (heap, 1578, NULL);
+   removed [1] = g_heap_index (heap, gint, 2289); g_heap_extract_index (heap, 2289, NULL);
+   removed [2] = g_heap_index (heap, gint, 3312); g_heap_extract_index (heap, 3312, NULL);
+   removed [3] = g_heap_index (heap, gint, 78901); g_heap_extract_index (heap, 78901, NULL);
+   removed [4] = g_heap_index (heap, gint, 99000); g_heap_extract_index (heap, 99000, NULL);
+
+   for (i = 0; i < 100000; i++) {
+      if (g_heap_peek (heap, gint) != i) {
+         g_assert ((i == removed[0]) ||
+                   (i == removed[1]) ||
+                   (i == removed[2]) ||
+                   (i == removed[3]) ||
+                   (i == removed[4]));
+      } else {
+         g_heap_extract (heap, &v);
+         g_assert_cmpint (v, ==, i);
+      }
+   }
+
+   g_assert_cmpint (heap->len, ==, 0);
+
+   g_heap_unref (heap);
+}
+
+int
+main (gint   argc,
+      gchar *argv[])
+{
+   g_test_init (&argc, &argv, NULL);
+   g_test_bug_base ("http://bugzilla.gnome.org/");
+
+   g_test_add_func ("/GHeap/insert_and_extract<gint>", test_GHeap_insert_val_int);
+   g_test_add_func ("/GHeap/insert_and_extract<gpointer>", test_GHeap_insert_val_ptr);
+   g_test_add_func ("/GHeap/insert_and_extract<Tuple>", test_GHeap_insert_val_tuple);
+   g_test_add_func ("/GHeap/extract_index<int>", test_GHeap_extract_int);
+
+   return g_test_run ();
+}