diff options
| author | mo khan <mo.khan@gmail.com> | 2020-09-20 19:21:51 -0600 |
|---|---|---|
| committer | mo khan <mo.khan@gmail.com> | 2020-09-20 19:21:51 -0600 |
| commit | 937998ed9985ba4a8babec55e9b7e17730d49d8f (patch) | |
| tree | 60ee0a653278c0ff00d96bef7a23e68a98e64eb8 /src/03 | |
| parent | 35fe546e0a2dd1aa95397d9e64911b2d848a0a78 (diff) | |
docs: add source code from book as starting point to modify
Diffstat (limited to 'src/03')
| -rw-r--r-- | src/03/07/README.md | 38 |
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) |
