diff options
| author | mo khan <mo.khan@gmail.com> | 2020-09-26 19:44:29 -0600 |
|---|---|---|
| committer | mo khan <mo.khan@gmail.com> | 2020-09-26 19:44:29 -0600 |
| commit | 5cb4ce51804e8bc60fef6f3e33ceaee0f05bacc6 (patch) | |
| tree | 58a88d84a8d826ae89a23d95d74404a1741bd3ba /src/03/07 | |
| parent | c93020800e852b17f4cf30fb867bccac88d61cbd (diff) | |
Collapse all questions into a single README
Diffstat (limited to 'src/03/07')
| -rw-r--r-- | src/03/07/README.md | 43 |
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`. |
