summaryrefslogtreecommitdiff
path: root/src/03/07
diff options
context:
space:
mode:
authormo khan <mo.khan@gmail.com>2020-09-26 19:44:29 -0600
committermo khan <mo.khan@gmail.com>2020-09-26 19:44:29 -0600
commit5cb4ce51804e8bc60fef6f3e33ceaee0f05bacc6 (patch)
tree58a88d84a8d826ae89a23d95d74404a1741bd3ba /src/03/07
parentc93020800e852b17f4cf30fb867bccac88d61cbd (diff)
Collapse all questions into a single README
Diffstat (limited to 'src/03/07')
-rw-r--r--src/03/07/README.md43
1 files changed, 0 insertions, 43 deletions
diff --git a/src/03/07/README.md b/src/03/07/README.md
deleted file mode 100644
index 9df3078..0000000
--- a/src/03/07/README.md
+++ /dev/null
@@ -1,43 +0,0 @@
-Implement the `remove(u)` method, that removes the node `u` from a
-`MeldableHeap`. This method should run in `O(log n)` expected time.
-
-```java
-class MeldableHeap {
- Node<T> merge(Node<T> h1, Node<T> h2) {
- if (h1 == nil) return h2;
- if (h2 == nil) return h1;
- if (compare(h2.x, h1.x) < 0) return merge(h2, h1);
-
- if (rand.nextBoolean()) {
- h1.left = merge(h1.left, h2);
- h1.left.parent = h1;
- } else {
- h1.right = merge(h1.right, h2);
- h1.right.parent = h1;
- }
- return h1;
- }
-
- boolean add(T x) {
- Node<T> u = newNode();
- u.x = x;
- r = merge(u, r);
- r.parent = nil;
- n++;
- return true;
- }
-
- T remove() {
- T x = r.x;
- r = merge(r.left, r.right);
- if (r != nil) r.parent = nil;
- n--;
- return x;
- }
-}
-```
-[Source](https://www.aupress.ca/app/uploads/120226_99Z_Morin_2013-Open_Data_Structures.pdf)
-
-
-
-An implementation of `meldable_heap_remove(u)` can be found in `./meldable_heap.c`.