diff --git a/docs/reference/glib/glib-docs.sgml b/docs/reference/glib/glib-docs.sgml
index b2741fd..958d68f 100644
--- a/docs/reference/glib/glib-docs.sgml
+++ b/docs/reference/glib/glib-docs.sgml
@@ -36,6 +36,7 @@
 <!ENTITY glib-Doubly-Linked-Lists SYSTEM "xml/linked_lists_double.xml">
 <!ENTITY glib-Singly-Linked-Lists SYSTEM "xml/linked_lists_single.xml">
 <!ENTITY glib-Double-ended-Queues SYSTEM "xml/queue.xml">
+<!ENTITY glib-Priority-Queues SYSTEM "xml/priority_queues.xml">
 <!ENTITY glib-Sequences SYSTEM "xml/sequence.xml">
 <!ENTITY glib-Trash-Stacks SYSTEM "xml/trash_stack.xml">
 <!ENTITY glib-Hash-Tables SYSTEM "xml/hash_tables.xml">
@@ -182,6 +183,7 @@ synchronize their operation.
     &glib-Doubly-Linked-Lists;
     &glib-Singly-Linked-Lists;
     &glib-Double-ended-Queues;
+    &glib-Priority-Queues;
     &glib-Sequences;
     &glib-Trash-Stacks;
     &glib-Hash-Tables;
diff --git a/docs/reference/glib/glib-sections.txt b/docs/reference/glib/glib-sections.txt
index d78fa4b..4e66264 100644
--- a/docs/reference/glib/glib-sections.txt
+++ b/docs/reference/glib/glib-sections.txt
@@ -1957,6 +1957,25 @@ g_queue_delete_link
 </SECTION>
 
 <SECTION>
+<TITLE>Priority Queues</TITLE>
+<FILE>priority_queues</FILE>
+
+GPQueue
+GPQueueHandle
+g_pqueue_new
+g_pqueue_free
+g_pqueue_is_empty
+g_pqueue_push
+g_pqueue_peek
+g_pqueue_pop
+g_pqueue_remove
+g_pqueue_priority_changed
+g_pqueue_priority_decreased
+g_pqueue_clear
+</SECTION>
+
+
+<SECTION>
 <TITLE>Sequences</TITLE>
 <FILE>sequence</FILE>
 
diff --git a/glib/Makefile.am b/glib/Makefile.am
index e2080fb..566fc20 100644
--- a/glib/Makefile.am
+++ b/glib/Makefile.am
@@ -133,6 +133,7 @@ libglib_2_0_la_SOURCES = 	\
 	gpattern.c		\
 	gpoll.c			\
 	gprimes.c		\
+	gpqueue.c		\
 	gqsort.c		\
 	gqueue.c		\
 	grel.c			\
diff --git a/glib/glib.h b/glib/glib.h
index f8acdd2..f519b84 100644
--- a/glib/glib.h
+++ b/glib/glib.h
@@ -62,6 +62,7 @@
 #include <glib/gpattern.h>
 #include <glib/gpoll.h>
 #include <glib/gprimes.h>
+#include <glib/gpqueue.h>
 #include <glib/gqsort.h>
 #include <glib/gquark.h>
 #include <glib/gqueue.h>
diff --git a/glib/glib.symbols b/glib/glib.symbols
index 6e3a63b..8432041 100644
--- a/glib/glib.symbols
+++ b/glib/glib.symbols
@@ -870,6 +870,21 @@ g_poll
 #endif
 #endif
 
+#if IN_HEADER(__G_PQUEUE_H__)
+#if IN_FILE(__G_PQUEUE_C__)
+g_pqueue_clear
+g_pqueue_free
+g_pqueue_is_empty
+g_pqueue_new
+g_pqueue_peek
+g_pqueue_pop
+g_pqueue_priority_changed
+g_pqueue_priority_decreased
+g_pqueue_push
+g_pqueue_remove
+#endif
+#endif
+
 #if IN_HEADER(__G_PRIMES_H__)
 #if IN_FILE(__G_PRIMES_C__)
 g_spaced_primes_closest G_GNUC_CONST
diff --git a/glib/gpqueue.c b/glib/gpqueue.c
new file mode 100644
index 0000000..01ee858
--- /dev/null
+++ b/glib/gpqueue.c
@@ -0,0 +1,715 @@
+#include "config.h"
+
+#include "glib.h"
+#include "galias.h"
+
+/**
+ * SECTION:priority_queues
+ * @short_description: a collection of data entries with associated priority
+ * values that returns entries one by one in order of priority
+ * 
+ * <para>
+ * The #GPQueue structure and its associated functions provide a sorted
+ * collection of objects. Entries can be inserted in any order and at any time,
+ * and an entry's priority can be changed after it has been inserted into the
+ * queue. Entries are supposed to be removed one at a time in order of priority
+ * with g_pqueue_pop(), but deleting entries out of order is possible.
+ * </para>
+ * <para>
+ * The entries <emphasis>cannot</emphasis> be iterated over in any way other
+ * than removing them one by one in order of priority, but when doing that,
+ * this structure is far more efficient than sorted lists or balanced trees,
+ * which on the other hand do not suffer from this restriction.
+ * </para>
+ * <para>
+ * You will want to be very careful with calls that use #GPQueueHandle.
+ * Handles immediately become invalid when an entry is removed from a #GPQueue,
+ * but the current implementation cannot detect this and will do unfortunate
+ * things to undefined memory locations if you try to use an invalid handle.
+ * </para>
+ * <note>
+ *   <para>
+ *     Internally, #GPQueue currently uses a Fibonacci heap to store
+ *     the entries. This implementation detail may change.
+ *   </para>
+ * </note>
+ **/
+
+#define IMPL_FIBONACCI_HEAP
+#undef  IMPL_BINARY_HEAP
+
+#if defined IMPL_FIBONACCI_HEAP
+struct _GPQueueNode {
+  GPQueueNode *next;
+  GPQueueNode *prev;
+  GPQueueNode *parent;
+  GPQueueNode *child;
+
+  gpointer data;
+
+  gint degree;
+  gboolean marked;
+};
+
+struct _GPQueue {
+  GPQueueNode *root;
+  GCompareDataFunc cmp;
+  gpointer *cmpdata;
+};
+#elif defined IMPL_BINARY_HEAP
+static const gsize GPQUEUE_INITIALSIZE = 16;
+
+struct _GPQueueNode {
+  gint index;
+  gpointer data;
+};
+
+struct _GPQueue {
+  GPQueueNode **array;
+  gsize size;
+  gsize maxsize;
+
+  GCompareDataFunc cmp;
+  gpointer *cmpdata;
+};
+#endif
+
+/**
+ * g_pqueue_new:
+ * @compare_func: the #GCompareDataFunc used to sort the new priority queue.
+ *   This function is passed two elements of the queue and should return 0 if
+ *   they are equal, a negative value if the first comes before the second, and
+ *   a positive value if the second comes before the first.
+ * @compare_userdata: user data passed to @compare_func
+ * 
+ * Creates a new #GPQueue.
+ * 
+ * Returns: a new #GPQueue.
+ * 
+ * Since: 2.x
+ **/
+GPQueue*
+g_pqueue_new (GCompareDataFunc compare_func,
+              gpointer *compare_userdata)
+{
+  g_return_val_if_fail (compare_func != NULL, NULL);
+
+  GPQueue *pqueue = g_slice_new (GPQueue);
+
+#if defined IMPL_FIBONACCI_HEAP
+  pqueue->root = NULL;
+#elif defined IMPL_BINARY_HEAP
+  pqueue->array = g_new (GPQueueNode*, GPQUEUE_INITIALSIZE);
+  pqueue->size = 0;
+  pqueue->maxsize = GPQUEUE_INITIALSIZE;
+#endif
+
+  pqueue->cmp = compare_func;
+  pqueue->cmpdata = compare_userdata;
+
+  return pqueue;
+}
+
+/**
+ * g_pqueue_is_empty:
+ * @pqueue: a #GPQueue.
+ * 
+ * Returns %TRUE if the queue is empty.
+ * 
+ * Returns: %TRUE if the queue is empty.
+ * 
+ * Since: 2.x
+ **/
+gboolean
+g_pqueue_is_empty (GPQueue *pqueue)
+{
+#if defined IMPL_FIBONACCI_HEAP
+  return (pqueue->root == NULL);
+#elif defined IMPL_BINARY_HEAP
+  return (pqueue->size == 0);
+#endif
+}
+
+static inline gint
+cmp (GPQueue *pqueue,
+     GPQueueNode *a,
+     GPQueueNode *b)
+{
+  return pqueue->cmp (a->data, b->data, pqueue->cmpdata);
+}
+
+#if defined IMPL_FIBONACCI_HEAP
+static inline void
+g_pqueue_node_cut (GPQueueNode *src)
+{
+  src->prev->next = src->next;
+  src->next->prev = src->prev;
+  src->next = src;
+  src->prev = src;
+}
+
+static inline void
+g_pqueue_node_insert_before (GPQueueNode *dest,
+                             GPQueueNode *src)
+{
+  GPQueueNode *prev;
+
+  prev = dest->prev;
+  dest->prev = src->prev;
+  src->prev->next = dest;
+  src->prev = prev;
+  prev->next = src;
+}
+
+static inline void
+g_pqueue_node_insert_after (GPQueueNode *dest,
+                            GPQueueNode *src)
+{
+  GPQueueNode *next;
+
+  next = dest->next;
+  dest->next = src;
+  src->prev->next = next;
+  next->prev = src->prev;
+  src->prev = dest;
+}
+#endif /* defined IMPL_FIBONACCI_HEAP */
+
+#if defined IMPL_BINARY_HEAP
+static inline void
+swap_entries (GPQueue* pqueue, gint i, gint j) {
+  GPQueueNode* ipointer = pqueue->array[i];
+  GPQueueNode* jpointer = pqueue->array[j];
+  pqueue->array[i] = jpointer;
+  pqueue->array[j] = ipointer;
+  ipointer->index = j;
+  jpointer->index = i;
+}
+
+static inline gint
+heapify_up (GPQueue* pqueue, gint i)
+{
+  gint parent;
+
+  while (i > 0) {
+    parent = (i - 1) / 2;
+    if (cmp (pqueue, pqueue->array[i], pqueue->array[parent]) < 0) {
+      swap_entries (pqueue, parent, i);
+      i = parent;
+    } else {
+      break;
+    }
+  }
+
+  return i;
+}
+
+static inline gint
+heapify_down (GPQueue* pqueue, gint i)
+{
+  gint child;
+
+  child = 2 * i + 1;
+  while (child < pqueue->size) {
+    if ( ((child + 1) < pqueue->size)
+         && (cmp (pqueue, pqueue->array[child + 1], pqueue->array[child]) < 0) ) {
+      child++;
+    }
+    if (cmp (pqueue, pqueue->array[child], pqueue->array[i]) < 0) {
+      swap_entries (pqueue, i, child);
+      i = child;
+      child = 2 * i + 1;
+    } else {
+      break;
+    }
+  }
+
+  return i;
+}
+
+static inline void
+heapify (GPQueue* pqueue, gint i)
+{
+  i = heapify_up (pqueue, i);
+  i = heapify_down (pqueue, i);
+  return i;
+}
+#endif /* defined IMPL_BINARY_HEAP */
+
+/**
+ * g_pqueue_push:
+ * @pqueue: a #GPQueue.
+ * @data: the object to insert into the priority queue.
+ * 
+ * Inserts a new entry into a #GPQueue.
+ * 
+ * The returned handle can be used in calls to g_pqueue_remove() and
+ * g_pqueue_priority_changed(). Never make such calls for entries that have
+ * already been removed from the queue. The same @data can be inserted into
+ * a #GPQueue more than once, but remember that in this case,
+ * g_pqueue_priority_changed() needs to be called for
+ * <emphasis>every</emphasis> handle for that object if its priority changes.
+ * 
+ * Returns: a handle for the freshly inserted entry.
+ * 
+ * Since: 2.x
+ **/
+GPQueueHandle
+g_pqueue_push (GPQueue *pqueue,
+               gpointer data)
+{
+  GPQueueNode *e;
+
+  e = g_slice_new (GPQueueNode);
+  e->data = data;
+
+#if defined IMPL_FIBONACCI_HEAP
+  e->next = e;
+  e->prev = e;
+  e->parent = NULL;
+  e->child = NULL;
+  e->degree = 0;
+  e->marked = FALSE;
+
+  if (pqueue->root != NULL) {
+    g_pqueue_node_insert_before (pqueue->root, e);
+    if (cmp (pqueue, e, pqueue->root) < 0)
+      pqueue->root = e;
+  } else {
+    pqueue->root = e;
+  }
+#elif defined IMPL_BINARY_HEAP
+  if (pqueue->size >= pqueue->maxsize) {
+    pqueue->maxsize *= 2;
+    pqueue->array = g_renew (GPQueueNode*, pqueue->array, pqueue->maxsize);
+  }
+
+  e->index = pqueue->size;
+  pqueue->array[e->index] = e;
+  (pqueue->size)++;
+  heapify_up (pqueue, e->index);
+#endif
+
+  return e;
+}
+
+/**
+ * g_pqueue_peek:
+ * @pqueue: a #GPQueue.
+ * 
+ * Returns the topmost entry's data pointer, or %NULL if the queue is empty.
+ * 
+ * If you need to tell the difference between an empty queue and a queue
+ * that happens to have a %NULL pointer at the top, check if the queue is
+ * empty first.
+ * 
+ * Returns: the topmost entry's data pointer, or %NULL if the queue is empty.
+ * 
+ * Since: 2.x
+ **/
+gpointer
+g_pqueue_peek (GPQueue *pqueue)
+{
+#if defined IMPL_FIBONACCI_HEAP
+  return (pqueue->root != NULL) ? pqueue->root->data : NULL;
+#elif defined IMPL_BINARY_HEAP
+  return (pqueue->size > 0) ? pqueue->array[0]->data : NULL;
+#endif
+}
+
+#if defined IMPL_FIBONACCI_HEAP
+static inline GPQueueNode*
+g_pqueue_make_child (GPQueueNode *a,
+                     GPQueueNode *b)
+{
+  g_pqueue_node_cut (b);
+  if (a->child != NULL) {
+    g_pqueue_node_insert_before (a->child, b);
+    a->degree += 1;
+  } else {
+    a->child = b;
+    a->degree = 1;
+  }
+  b->parent = a;
+  return a;
+}
+
+static inline GPQueueNode*
+g_pqueue_join_trees (GPQueue *pqueue,
+                     GPQueueNode *a,
+                     GPQueueNode *b)
+{
+  if (cmp (pqueue, a, b) < 0)
+    return g_pqueue_make_child (a, b);
+  return g_pqueue_make_child (b, a);
+}
+
+static void
+g_pqueue_fix_rootlist (GPQueue* pqueue)
+{
+  gsize degnode_size;
+  GPQueueNode **degnode;
+  GPQueueNode sentinel;
+  GPQueueNode *current;
+  GPQueueNode *minimum;
+
+  /* We need to iterate over the circular list we are given and do
+   * several things:
+   * - Make sure all the elements are unmarked
+   * - Make sure to return the element in the list with smallest
+   *   priority value
+   * - Find elements of identical degree and join them into trees
+   * The last point is irrelevant for correctness, but essential
+   * for performance. If we did not do this, our data structure would
+   * degrade into an unsorted linked list.
+   */
+
+  degnode_size = (8 * sizeof(gpointer) + 1) * sizeof(gpointer);
+  degnode = g_slice_alloc0 (degnode_size);
+
+  sentinel.next = &sentinel;
+  sentinel.prev = &sentinel;
+  g_pqueue_node_insert_before (pqueue->root, &sentinel);
+
+  current = pqueue->root;
+  while (current != &sentinel) {
+    current->marked = FALSE;
+    current->parent = NULL;
+    gint d = current->degree;
+    if (degnode[d] == NULL) {
+      degnode[d] = current;
+      current = current->next;
+    } else {
+      if (degnode[d] != current) {
+        current = g_pqueue_join_trees (pqueue, degnode[d], current);
+        degnode[d] = NULL;
+      } else {
+        current = current->next;
+      }
+    }
+  }
+
+  current = sentinel.next;
+  minimum = current;
+  while (current != &sentinel) {
+    if (cmp (pqueue, current, minimum) < 0)
+      minimum = current;
+    current = current->next;
+  }
+  pqueue->root = minimum;
+
+  g_pqueue_node_cut (&sentinel);
+
+  g_slice_free1 (degnode_size, degnode);
+}
+
+static void
+g_pqueue_remove_root (GPQueue *pqueue,
+                      GPQueueNode *root)
+{
+  /* This removes a node at the root _level_ of the structure, which can be,
+   * but does not have to be, the actual pqueue->root node. That is why
+   * we require an explicit pointer to the node to be removed instead of just
+   * removing pqueue->root implictly.
+   */
+
+  /* Step one:
+   * If root has any children, pull them up to root level.
+   * At this time, we only deal with their next/prev pointers,
+   * further changes are made later in g_pqueue_fix_rootlist().
+   */
+  if (root->child) {
+    g_pqueue_node_insert_after (root, root->child);
+    root->child = NULL;
+    root->degree = 0;
+  }
+
+  /* Step two:
+   * Cut root out of the list.
+   */
+  if (root->next != root) {
+    pqueue->root = root->next;
+    g_pqueue_node_cut (root);
+    /* Step three:
+     * Clean up the remaining list.
+     */
+    g_pqueue_fix_rootlist (pqueue);
+  } else {
+    pqueue->root = NULL;
+  }
+
+  g_slice_free (GPQueueNode, root);
+}
+#endif /* defined IMPL_FIBONACCI_HEAP */
+
+/**
+ * g_pqueue_pop:
+ * @pqueue: a #GPQueue.
+ * 
+ * Removes the topmost entry from a #GPQueue and returns its data pointer.
+ * Calling this on an empty #GPQueue is not an error, but removes nothing
+ * and returns %NULL.
+ * 
+ * If you need to tell the difference between an empty queue and a queue
+ * that happens to have a %NULL pointer at the top, check if the queue is
+ * empty first.
+ * 
+ * Returns: the topmost entry's data pointer, or %NULL if the queue was empty.
+ * 
+ * Since: 2.x
+ **/
+gpointer
+g_pqueue_pop (GPQueue *pqueue)
+{
+  gpointer data;
+
+#if defined IMPL_FIBONACCI_HEAP
+  if (pqueue->root == NULL) return NULL;
+  data = pqueue->root->data;
+  g_pqueue_remove_root (pqueue, pqueue->root);
+#elif defined IMPL_BINARY_HEAP
+  if (pqueue->size == 0) return NULL;
+  data = pqueue->array[0]->data;
+  (pqueue->size)--;
+
+  swap_entries (pqueue, 0, pqueue->size);
+  heapify_down (pqueue, 0);
+
+  g_slice_free (GPQueueNode, pqueue->array[pqueue->size]);
+
+  if ( (pqueue->maxsize > GPQUEUE_INITIALSIZE)
+       && (pqueue->size < (pqueue->maxsize / 4)) ) {
+    pqueue->maxsize /= 2;
+    pqueue->array = g_renew (GPQueueNode*, pqueue->array, pqueue->maxsize);
+  }
+#endif
+
+  return data;
+}
+
+#if defined IMPL_FIBONACCI_HEAP
+static inline void
+g_pqueue_make_root (GPQueue *pqueue,
+                    GPQueueNode *entry)
+{
+  /* This moves a node up to the root _level_ of the structure.
+   * It does not always become the actual root element (pqueue->root).
+   */
+
+  GPQueueNode *parent;
+
+  parent = entry->parent;
+  entry->parent = NULL;
+  entry->marked = FALSE;
+  if (parent != NULL) {
+    if (entry->next != entry) {
+      if (parent->child == entry) parent->child = entry->next;
+      g_pqueue_node_cut (entry);
+      parent->degree -= 1;
+    } else {
+      parent->child = NULL;
+      parent->degree = 0;
+    }
+    g_pqueue_node_insert_before (pqueue->root, entry);
+  }
+
+  if (cmp (pqueue, entry, pqueue->root) < 0)
+    pqueue->root = entry;
+}
+
+static void
+g_pqueue_cut_tree (GPQueue *pqueue,
+                   GPQueueNode *entry)
+{
+  /* This function moves an entry up to the root level of the structure.
+   * It extends g_pqueue_make_root() in that the entry's parent, grandparent
+   * etc. may also be moved to the root level if they are "marked". This is
+   * not essential for correctness, it just maintains the so-called "potential"
+   * of the structure, which is necessary for the amortized runtime analysis.
+   */
+
+  GPQueueNode *current;
+  GPQueueNode *parent;
+
+  current = entry;
+  while ((current != NULL) && (current->parent != NULL)) {
+    parent = current->parent;
+    g_pqueue_make_root (pqueue, entry);
+    if (parent->marked) {
+      current = parent;
+    } else {
+      parent->marked = TRUE;
+      current = NULL;
+    }
+  }
+  if (cmp (pqueue, entry, pqueue->root) < 0)
+    pqueue->root = entry;
+}
+#endif /* defined IMPL_FIBONACCI_HEAP */
+
+/**
+ * g_pqueue_remove:
+ * @pqueue: a #GPQueue.
+ * @entry: a #GPQueueHandle for an entry in @pqueue.
+ * 
+ * Removes one entry from a #GPQueue.
+ * 
+ * Make sure that @entry refers to an entry that is actually part of
+ * @pqueue at the time, otherwise the behavior of this function is
+ * undefined (expect crashes).
+ * 
+ * Since: 2.x
+ **/
+void
+g_pqueue_remove (GPQueue* pqueue,
+                 GPQueueHandle entry)
+{
+#if defined IMPL_FIBONACCI_HEAP
+  g_pqueue_cut_tree (pqueue, entry);
+  g_pqueue_remove_root (pqueue, entry);
+#elif defined IMPL_BINARY_HEAP
+  gint i = entry->index;
+  (pqueue->size)--;
+  swap_entries (pqueue, i, pqueue->size);
+  g_slice_free (GPQueueNode, pqueue->array[pqueue->size]);
+  heapify (pqueue, i);
+#endif
+}
+
+/**
+ * g_pqueue_priority_changed:
+ * @pqueue: a #GPQueue.
+ * @entry: a #GPQueueHandle for an entry in @pqueue.
+ * 
+ * Notifies the #GPQueue that the priority of one entry has changed.
+ * The internal representation is updated accordingly.
+ * 
+ * Make sure that @entry refers to an entry that is actually part of
+ * @pqueue at the time, otherwise the behavior of this function is
+ * undefined (expect crashes).
+ * 
+ * Do not attempt to change the priorities of several entries at once.
+ * Every time a single object is changed, the #GPQueue needs to be updated
+ * by calling g_pqueue_priority_changed() for that object.
+ * 
+ * Since: 2.x
+ **/
+void
+g_pqueue_priority_changed (GPQueue* pqueue,
+                           GPQueueHandle entry)
+{
+#if defined IMPL_FIBONACCI_HEAP
+  g_pqueue_cut_tree (pqueue, entry);
+
+  if (entry->child) {
+    g_pqueue_node_insert_after (entry, entry->child);
+    entry->child = NULL;
+    entry->degree = 0;
+  }
+
+  g_pqueue_fix_rootlist (pqueue);
+#elif defined IMPL_BINARY_HEAP
+  heapify (pqueue, entry->index);
+#endif
+}
+
+/**
+ * g_pqueue_priority_decreased:
+ * @pqueue: a #GPQueue.
+ * @entry: a #GPQueueHandle for an entry in @pqueue.
+ * 
+ * Notifies the #GPQueue that the priority of one entry has
+ * <emphasis>decreased</emphasis>.
+ * 
+ * This is a special case of g_pqueue_priority_changed(). If you are absolutely
+ * sure that the new priority of @entry is lower than it was before, you
+ * may call this function instead of g_pqueue_priority_changed().
+ * 
+ * <note>
+ *   <para>
+ *     In the current implementation, an expensive step in
+ *     g_pqueue_priority_changed() can be skipped if the new priority is known
+ *     to be lower, leading to an amortized running time of O(1) instead of
+ *     O(log n). Of course, if the priority is not actually lower, behavior
+ *     is undefined.
+ *   </para>
+ * </note>
+ * 
+ * Since: 2.x
+ **/
+void
+g_pqueue_priority_decreased (GPQueue* pqueue,
+                             GPQueueHandle entry)
+{
+#if defined IMPL_FIBONACCI_HEAP
+  g_pqueue_cut_tree (pqueue, entry);
+#elif defined IMPL_BINARY_HEAP
+  heapify_up (pqueue, entry->index);
+#endif
+}
+
+#if defined IMPL_FIBONACCI_HEAP
+static void
+g_pqueue_node_free_all (GPQueueNode *node)
+{
+  if (node == NULL) return;
+  g_pqueue_node_free_all (node->child);
+  node->prev->next = NULL;
+  g_pqueue_node_free_all (node->next);
+  g_slice_free (GPQueueNode, node);
+}
+#endif /* defined IMPL_FIBONACCI_HEAP */
+
+/**
+ * g_pqueue_clear:
+ * @pqueue: a #GPQueue.
+ * 
+ * Removes all entries from a @pqueue.
+ * 
+ * Since: 2.x
+ **/
+void
+g_pqueue_clear (GPQueue* pqueue)
+{
+#if defined IMPL_FIBONACCI_HEAP
+  g_pqueue_node_free_all (pqueue->root);
+  pqueue->root = NULL;
+#elif defined IMPL_BINARY_HEAP
+  gint i;
+  for (i = 0; i < pqueue->size; i++) {
+    g_slice_free (GPQueueNode, pqueue->array[i]);
+  }
+  pqueue->size = 0;
+  g_free (pqueue->array);
+  pqueue->array = g_new (GPQueueNode*, GPQUEUE_INITIALSIZE);
+#endif
+}
+
+/**
+ * g_pqueue_free:
+ * @pqueue: a #GPQueue.
+ * 
+ * Deallocates the memory used by @pqueue itself, but not any memory pointed
+ * to by the data pointers of its entries.
+ * 
+ * Since: 2.x
+ **/
+void
+g_pqueue_free (GPQueue* pqueue)
+{
+#if defined IMPL_FIBONACCI_HEAP
+  g_pqueue_clear (pqueue);
+  g_slice_free (GPQueue, pqueue);
+#elif defined IMPL_BINARY_HEAP
+  gint i;
+  for (i = 0; i < pqueue->size; i++) {
+    g_slice_free (GPQueueNode, pqueue->array[i]);
+  }
+  g_free (pqueue->array);
+  g_slice_free (GPQueue, pqueue);
+#endif
+}
+
+#define __G_PQUEUE_C__
+#include "galiasdef.c"
+
diff --git a/glib/gpqueue.h b/glib/gpqueue.h
new file mode 100644
index 0000000..857c2ad
--- /dev/null
+++ b/glib/gpqueue.h
@@ -0,0 +1,58 @@
+#if defined(G_DISABLE_SINGLE_INCLUDES) && !defined (__GLIB_H_INSIDE__) && !defined (GLIB_COMPILATION)
+#error "Only <glib.h> can be included directly."
+#endif
+
+#ifndef __G_PQUEUE_H__
+#define __G_PQUEUE_H__
+
+G_BEGIN_DECLS
+
+typedef struct _GPQueueNode GPQueueNode;
+
+/**
+ * GPQueue:
+ * 
+ * An opaque structure representing a priority queue.
+ * 
+ * Since: 2.x
+ **/
+typedef struct _GPQueue GPQueue;
+
+/**
+ * GPQueueHandle:
+ * 
+ * An opaque value representing one entry in a #GPQueue.
+ * 
+ * Since: 2.x
+ **/
+typedef GPQueueNode* GPQueueHandle;
+
+GPQueue*	g_pqueue_new			(GCompareDataFunc compare_func,
+						 gpointer *compare_userdata);
+
+void		g_pqueue_free			(GPQueue* pqueue);
+
+gboolean	g_pqueue_is_empty		(GPQueue *pqueue);
+
+GPQueueHandle	g_pqueue_push			(GPQueue *pqueue,
+						 gpointer data);
+
+gpointer	g_pqueue_peek			(GPQueue *pqueue);
+
+gpointer	g_pqueue_pop			(GPQueue *pqueue);
+
+void		g_pqueue_remove			(GPQueue* pqueue,
+						 GPQueueHandle entry);
+
+void		g_pqueue_priority_changed	(GPQueue* pqueue,
+						 GPQueueHandle entry);
+
+void		g_pqueue_priority_decreased	(GPQueue* pqueue,
+						 GPQueueHandle entry);
+
+void		g_pqueue_clear			(GPQueue* pqueue);
+
+G_END_DECLS
+
+#endif /* __G_PQUEUE_H__ */
+
diff --git a/glib/tests/Makefile.am b/glib/tests/Makefile.am
index 673d338..c40766c 100644
--- a/glib/tests/Makefile.am
+++ b/glib/tests/Makefile.am
@@ -38,6 +38,10 @@ TEST_PROGS        += string
 string_SOURCES     = string.c
 string_LDADD	   = $(progs_ldadd) -lm
 
+TEST_PROGS        += pqueues
+pqueues_SOURCES    = pqueues.c
+pqueues_LDADD      = $(progs_ldadd) -lm
+
 TEST_PROGS               += markup-subparser
 markup_subparser_LDADD    = $(progs_ldadd)
 
diff --git a/glib/tests/pqueues.c b/glib/tests/pqueues.c
new file mode 100644
index 0000000..6faf65a
--- /dev/null
+++ b/glib/tests/pqueues.c
@@ -0,0 +1,242 @@
+#include <string.h>
+#include "glib.h"
+
+#define COUNT 100000
+const gint p_min = 0;
+const gint p_max = 9999;
+
+GPQueue *q;
+gint *input;
+GPQueueHandle *handles;
+GQueue *groups;
+gint **output;
+
+static inline gint
+ranp (void)
+{
+  return g_test_rand_int_range (p_min, p_max + 1);
+}
+
+static gint
+entrycmp (gint *a, gint *b, gpointer data)
+{
+  return *a - *b;
+}
+
+static void
+prepare (void)
+{
+  gint i;
+
+  q = g_pqueue_new ((GCompareDataFunc)entrycmp, NULL);
+  input = g_new (gint, COUNT);
+  handles = g_new (GPQueueHandle, COUNT);
+  groups = g_queue_new ();
+  output = g_new (gint*, COUNT);
+
+  for (i = 0; i < COUNT; i++) input[i] = ranp ();
+}
+
+static void
+verify (gint i, gint j)
+{
+  gint k, a, b;
+
+  /* Verify that the right number of elements were pushed and popped */
+  g_assert_cmpint (i, ==, COUNT);
+  g_assert_cmpint (j, <=, i);
+
+  /* Verify that the entries were returned in a valid order */
+  i = 0;
+  while (!g_queue_is_empty (groups)) {
+    j = GPOINTER_TO_INT(g_queue_pop_head (groups));
+    a = *(output[i]);
+    for (k = i + 1; k < j; k++) {
+      b = *(output[k]);
+      g_assert_cmpint (a, <=, b);
+      a = b;
+    }
+    i = j;
+  }
+
+  /* Verify that each entry was returned exactly once */
+  for (j = 0; j < COUNT; j++) {
+    g_assert (output[j] >= input);
+    g_assert (output[j] < input + COUNT);
+    *(output[j]) = -1;
+  }
+  for (i = 0; i < COUNT; i++) g_assert_cmpint (input[i], ==, -1);
+}
+
+static void
+cleanup (void)
+{
+  g_free (output);
+  g_queue_free (groups);
+  g_free (handles);
+  g_free (input);
+  g_pqueue_free (q);
+}
+
+static void
+push (gint i)
+{
+  g_assert_cmpint (i, <, COUNT);
+  handles[i] = g_pqueue_push (q, input + i);
+}
+
+static void
+pop (gint i)
+{
+  g_assert_cmpint (i, <, COUNT);
+  output[i] = g_pqueue_pop (q);
+  handles[output[i] - input] = NULL;
+}
+
+static void
+change_prio (gint i)
+{
+  if (handles[i] != NULL) {
+    gint new_p = ranp ();
+    gint old_p = input[i];
+    input[i] = new_p;
+    if (new_p < old_p) g_pqueue_priority_decreased (q, handles[i]);
+    else g_pqueue_priority_changed (q, handles[i]);
+  }
+}
+
+static void
+test_pushpop_all (void)
+{
+  gint i, j;
+
+  prepare ();
+
+  g_test_timer_start ();
+  for (i = 0; i < COUNT; i++) push (i);
+  j = 0;
+  while (!g_pqueue_is_empty (q)) pop (j++);
+  g_queue_push_tail (groups, GINT_TO_POINTER(j));
+  double runtime = g_test_timer_elapsed ();
+
+  verify (i, j);
+
+  g_test_minimized_result (runtime,
+    "Time to push %d elements, then pop everything: %.3f", COUNT, runtime);
+
+  cleanup ();
+}
+
+static void
+test_pushpop_rand (void)
+{
+  gint i, j;
+
+  prepare ();
+
+  i = j = 0;
+  g_test_timer_start ();
+  while (i < COUNT) {
+    gint pushes = g_test_rand_int_range (1, COUNT / 10);
+    if (pushes > COUNT - i) pushes = COUNT - i;
+    while (pushes > 0) {
+      push (i);
+      i++;
+      pushes--;
+    }
+    gint pops = g_test_rand_int_range (1, COUNT / 10);
+    while ((!g_pqueue_is_empty (q)) && (pops > 0)) {
+      pop (j);
+      j++;
+      pops--;
+    }
+    g_queue_push_tail (groups, GINT_TO_POINTER(j));
+  }
+  while (!g_pqueue_is_empty (q)) pop (j++);
+  double runtime = g_test_timer_elapsed ();
+
+  verify (i, j);
+
+  g_test_minimized_result (runtime,
+    "Time to push and pop %d elements at random: %.3f", COUNT, runtime);
+
+  cleanup ();
+}
+
+static void
+test_pushchangepop (void)
+{
+  gint i, j, k;
+
+  prepare ();
+
+  g_test_timer_start ();
+  for (i = 0; i < COUNT; i++) push (i);
+  for (k = 0; k < COUNT / 10; k++) change_prio (g_test_rand_int_range (0, i));
+  j = 0;
+  while (!g_pqueue_is_empty (q)) pop (j++);
+  g_queue_push_tail (groups, GINT_TO_POINTER(j));
+  double runtime = g_test_timer_elapsed ();
+
+  verify (i, j);
+
+  g_test_minimized_result (runtime,
+    "Time to push %d elements, change %d priorities, then pop everything: %.3f",
+    COUNT, COUNT / 10, runtime);
+
+  cleanup ();
+}
+
+static void
+test_pushchangepop_rand (void)
+{
+  gint i, j, k;
+
+  prepare ();
+
+  i = j = 0;
+  g_test_timer_start ();
+  while (i < COUNT) {
+    gint pushes = g_test_rand_int_range (1, COUNT / 10);
+    if (pushes > COUNT - i) pushes = COUNT - i;
+    while (pushes > 0) {
+      push (i);
+      i++;
+      pushes--;
+    }
+    gint changes = g_test_rand_int_range (1, i / 10);
+    for (k = 0; k < changes; k++) change_prio (g_test_rand_int_range (0, i));
+    gint pops = g_test_rand_int_range (1, COUNT / 10);
+    while ((!g_pqueue_is_empty (q)) && (pops > 0)) {
+      pop (j);
+      j++;
+      pops--;
+    }
+    g_queue_push_tail (groups, GINT_TO_POINTER(j));
+  }
+  while (!g_pqueue_is_empty (q)) pop (j++);
+  double runtime = g_test_timer_elapsed ();
+
+  verify (i, j);
+
+  g_test_minimized_result (runtime,
+    "Time to push, change and pop %d elements at random: %.3f", COUNT, runtime);
+
+  cleanup ();
+}
+
+int
+main (int   argc,
+      char *argv[])
+{
+  g_test_init (&argc, &argv, NULL);
+
+  g_test_add_func ("/pqueue/pushpop_all", test_pushpop_all);
+  g_test_add_func ("/pqueue/pushpop_rand", test_pushpop_rand);
+  g_test_add_func ("/pqueue/pushchangepop", test_pushchangepop);
+  g_test_add_func ("/pqueue/pushchangepop_rand", test_pushchangepop_rand);
+
+  int result = g_test_run ();
+
+  return result;
+}
