From 6b01c947c2a572e20744f369cd07844928c9c117 Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <paul.jungeblut@gmail.com>
Date: Fri, 17 Nov 2017 20:18:14 +0100
Subject: Adding code for skew heaps.

---
 datastructures/skewHeap.cpp | 29 +++++++++++++++++++++++++++++
 1 file changed, 29 insertions(+)
 create mode 100644 datastructures/skewHeap.cpp

(limited to 'datastructures/skewHeap.cpp')

diff --git a/datastructures/skewHeap.cpp b/datastructures/skewHeap.cpp
new file mode 100644
index 0000000..ae2cc75
--- /dev/null
+++ b/datastructures/skewHeap.cpp
@@ -0,0 +1,29 @@
+// Skew Heap, verschmelzbare Priority Queue.
+// Laufzeit: Merging, Inserting, DeleteMin: O(log(n)) amortisiert
+struct node{
+  int key;
+  node *lc, *rc;
+  node(int k) : key(k), lc(0), rc(0) {}
+} *root = 0; 
+int size = 0;
+
+node* merge(node *x, node *y) {
+  if (!x) return y;
+  if (!y) return x;
+  if (x->key > y->key) swap(x,y);
+  x->rc = merge(x->rc, y);
+  swap(x->lc, x->rc);
+  return x;
+}
+
+void insert(int x) { root = merge(root, new node(x)); size++; }
+
+int delmin() {
+  if (!root) return -1;
+  int ret = root->key;
+  node *troot = merge(root->lc, root->rc);
+  delete root;
+  root = troot;
+  size--;
+  return ret;
+}
-- 
cgit v1.2.3