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/datastructures.tex |   4 +++-
 datastructures/skewHeap.cpp       |  29 +++++++++++++++++++++++++++++
 tcr.pdf                           | Bin 298283 -> 299733 bytes
 3 files changed, 32 insertions(+), 1 deletion(-)
 create mode 100644 datastructures/skewHeap.cpp

diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex
index 7659a7e..20dec7f 100644
--- a/datastructures/datastructures.tex
+++ b/datastructures/datastructures.tex
@@ -11,7 +11,6 @@ Dazu: Offset in den inneren Knoten des Baums speichern.
 \subsection{Fenwick Tree}
 \lstinputlisting{datastructures/fenwickTree.cpp}
 
-
 \subsection{Range Minimum Query}
 \lstinputlisting{datastructures/RMQ.cpp}
 
@@ -23,3 +22,6 @@ Dazu: Offset in den inneren Knoten des Baums speichern.
 
 \subsection{Treap (Cartesian Tree)}
 \lstinputlisting{datastructures/treap.cpp}
+
+\subsection{Skew Heap}
+\lstinputlisting{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;
+}
diff --git a/tcr.pdf b/tcr.pdf
index fe42202..b1f3847 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
-- 
cgit v1.2.3