ref: 6c9eb7f74993179a823f4e1c02793786d51bf773
author: qwx <qwx@sciops.net>
date: Tue Aug 11 07:33:22 EDT 2020
add pairing heaps
--- /dev/null
+++ b/fns.h
@@ -1,0 +1,4 @@
+void nukequeue(Pairheap**);
+Pairheap* popqueue(Pairheap**);
+void decreasekey(Pairheap*, double, Pairheap**);
+void pushqueue(double, void*, Pairheap**);
--- /dev/null
+++ b/heap.h
@@ -1,0 +1,9 @@
+typedef struct Pairheap Pairheap;
+
+struct Pairheap{+ double n;
+ void *aux;
+ Pairheap *parent;
+ Pairheap *left;
+ Pairheap *right;
+};
--- /dev/null
+++ b/pheap.c
@@ -1,0 +1,83 @@
+#include <u.h>
+#include <libc.h>
+#include "heap.h"
+#include "fns.h"
+
+static Pairheap *
+mergequeue(Pairheap *a, Pairheap *b)
+{+ if(b == nil)
+ return a;
+ else if(a->n < b->n){+ b->right = a->left;
+ a->left = b;
+ b->parent = a;
+ return a;
+ }else{+ a->right = b->left;
+ b->left = a;
+ a->parent = b;
+ return b;
+ }
+}
+
+static Pairheap *
+mergepairs(Pairheap *a)
+{+ Pairheap *b, *c;
+
+ if(a == nil)
+ return nil;
+ a->parent = nil;
+ b = a->right;
+ if(b == nil)
+ return a;
+ a->right = nil;
+ b->parent = nil;
+ c = b->right;
+ b->right = nil;
+ return mergequeue(mergequeue(a, b), mergepairs(c));
+}
+
+void
+nukequeue(Pairheap **queue)
+{+ Pairheap *p;
+
+ while((p = popqueue(queue)) != nil)
+ free(p);
+}
+
+Pairheap *
+popqueue(Pairheap **queue)
+{+ Pairheap *p;
+
+ p = *queue;
+ if(p == nil)
+ return nil;
+ *queue = mergepairs(p->left);
+ return p;
+}
+
+void
+decreasekey(Pairheap *p, double Δ, Pairheap **queue)
+{+ p->n -= Δ;
+ if(p->parent != nil && p->n < p->parent->n){+ p->parent->left = nil;
+ p->parent = nil;
+ *queue = mergequeue(p, *queue);
+ }
+}
+
+void
+pushqueue(int n, void *aux, Pairheap **queue)
+{+ Pairheap *p;
+
+ p = emalloc(sizeof *p);
+ p->n = n;
+ p->aux = aux;
+ *queue = mergequeue(p, *queue);
+}