From b8dc20e2a9be3fc3053885a557c23bda8833a670 Mon Sep 17 00:00:00 2001
From: Markus Himmel <markus@himmel-villmar.de>
Date: Mon, 21 May 2018 21:05:36 +0200
Subject: Remove Skew Heaps and add STL PQs

---
 datastructures/datastructures.tex |   5 +++--
 datastructures/skewHeap.cpp       |  29 -----------------------------
 datastructures/stlPQ.cpp          |  14 ++++++++++++++
 tcr.pdf                           | Bin 327319 -> 326648 bytes
 4 files changed, 17 insertions(+), 31 deletions(-)
 delete mode 100644 datastructures/skewHeap.cpp
 create mode 100644 datastructures/stlPQ.cpp

diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex
index a31edef..1c529a4 100644
--- a/datastructures/datastructures.tex
+++ b/datastructures/datastructures.tex
@@ -25,8 +25,9 @@
 \subsection{Treap (Cartesian Tree)}
 \lstinputlisting{datastructures/treap.cpp}
 
-\subsection{Skew Heap}
-\lstinputlisting{datastructures/skewHeap.cpp}
+\subsection{STL Priority Queue}
+Nicht notwendig, wenn Smaller-Larger-Optimization greift.
+\lstinputlisting{datastructures/stlPQ.cpp}
 
 \subsection{Lower/Upper Envelop (Convex Hull Optimization)}
 Um aus einem lower envelope einen upper envelope zu machen (oder umgekehrt), einfach beim Einfügen der Geraden $m$ und $b$ negieren.
diff --git a/datastructures/skewHeap.cpp b/datastructures/skewHeap.cpp
deleted file mode 100644
index ae2cc75..0000000
--- a/datastructures/skewHeap.cpp
+++ /dev/null
@@ -1,29 +0,0 @@
-// 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/datastructures/stlPQ.cpp b/datastructures/stlPQ.cpp
new file mode 100644
index 0000000..1de4abf
--- /dev/null
+++ b/datastructures/stlPQ.cpp
@@ -0,0 +1,14 @@
+#include <ext/pb_ds/priority_queue.hpp>
+template<typename T>
+using priorityQueue = __gnu_pbds::priority_queue<T, less<T>>; // greater<T> für Min-Queue
+
+int main() {
+	priorityQueue<int> pq;
+	auto it = pq.push(5); // O(1)
+	pq.push(7);
+	pq.pop(); // O(log n) amortisiert
+	pq.modify(it, 6); // O(log n) amortisiert
+	pq.erase(it); // O(log n) amortisiert
+	priorityQueue<int> pq2;
+	pq.join(pq2); // O(1)
+}
diff --git a/tcr.pdf b/tcr.pdf
index 2e4d8cd..eb97fc7 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
-- 
cgit v1.2.3