diff options
| -rw-r--r-- | datastructures/datastructures.tex | 5 | ||||
| -rw-r--r-- | datastructures/skewHeap.cpp | 29 | ||||
| -rw-r--r-- | datastructures/stlPQ.cpp | 14 | ||||
| -rw-r--r-- | tcr.pdf | bin | 327319 -> 326648 bytes |
4 files changed, 17 insertions, 31 deletions
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) +} Binary files differ |