diff options
| -rw-r--r-- | datastructures/datastructures.tex | 4 | ||||
| -rw-r--r-- | datastructures/skewHeap.cpp | 29 | ||||
| -rw-r--r-- | tcr.pdf | bin | 298283 -> 299733 bytes |
3 files changed, 32 insertions, 1 deletions
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; +} Binary files differ |