summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authormo khan <mo.khan@gmail.com>2020-09-20 19:21:51 -0600
committermo khan <mo.khan@gmail.com>2020-09-20 19:21:51 -0600
commit937998ed9985ba4a8babec55e9b7e17730d49d8f (patch)
tree60ee0a653278c0ff00d96bef7a23e68a98e64eb8 /src
parent35fe546e0a2dd1aa95397d9e64911b2d848a0a78 (diff)
docs: add source code from book as starting point to modify
Diffstat (limited to 'src')
-rw-r--r--src/03/07/README.md38
1 files changed, 38 insertions, 0 deletions
diff --git a/src/03/07/README.md b/src/03/07/README.md
index 8e85bde..20b320e 100644
--- a/src/03/07/README.md
+++ b/src/03/07/README.md
@@ -1,2 +1,40 @@
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)