Question
Implement the remove(u) method, that removes the node u from a MeldableHeap. This method should run in O(log n) expected time. JAVA
All other questions similiar to this are incorrectly answered. Someone typically just copy/pastes the general coding of a meldable/mergable heap and doesnt actually bother with changing the "remove()" method to "remove(u)".
I assume I need a find() method to do this as well, which the coding for would be greatly appreciated as I havent the slightest clue how to search the heap tree.
Explanation / Answer
/** ** Java Program to Implement Meldable Heap **/ import java.util.Scanner; import java.util.Random; /** Class Node **/ class Node { Node left, right, parent; int x; public Node(Node parent, Node left, Node right, int x) { this.parent = parent; this.left = left; this.right = right; this.x = x; } } /** Class MedlableHeap **/ class MeldableHeap { private Random rand; private int n; private Node root; public MeldableHeap() { root = null; rand = new Random(); n = 0; } /** Check if heap is empty **/ public boolean isEmpty() { return root == null; } /** clear heap **/ public void makeEmpty() { root = null; rand = new Random(); n = 0; } /** function to get size **/ public int getSize() { return n; } /** function to insert an element **/ public void add(int x) { Node u = new Node(null, null, null, x); root = meld(u, root); root.parent = null; n++; } /** function to remove an element **/ public int remove() { int x = root.x; root = meld(root.left, root.right); if (root != null) root.parent = null; n--; return x; } /** function to merge two nodes **/ public Node meld(Node q1, Node q2) { if (q1 == null) return q2; if (q2 == null) return q1; if (q2.x