I was doing reading on weighted quick-union using path compression. I have a clear understanding of why this is $O(1)$ with amortized analysis for union and find operations but do not understand how to address this special case.

Suppose we have $x$ items to start with, (all disjoint) and we perform a sequence of $m$ operations such that all calls to find come after all calls to union. I am trying to determine what kind of data structure could be used, because in my previous understanding of disjoint sets, the union operation is always dependent on the find operation.

Despite having this information about the order of operations, I do not quite see how it is useful- or, how it can be used to achieve an amortized analysis of $O(1)$. Also, not sure of how to approach the union operation without relying on calls to find.

  • $\begingroup$ You may refer this, it may solve your doubts. Data structure can be a simple array or array of structs where each struct is a node which contains parent id (or root id), node id, etc. WQUPC can lead to constant amortized cost since its complexity is O(N + M lg* N) and lg* N leads to very small values for large inputs (as stated in the link). Note that, in this approach, find operation is not needed when doing union, instead a operation to find parent (or root) is needed. $\endgroup$ – kiner_shah Nov 23 at 11:18
  • $\begingroup$ Thank you @kiner_shah. I suppose then my main confusion is the difference between find method and the root method- wouldn't both of these then tell us in which group an element is located? $\endgroup$ – rubyquartz Nov 23 at 18:48
  • $\begingroup$ Basically, find method is used to check if two elements belong to same group i.e. whether they are connected. root method is used to just get the group id of the group an element belongs to. So, both methods are different. If you just want to know which group an element belong to, then use root method. $\endgroup$ – kiner_shah Nov 24 at 6:40
  • $\begingroup$ find method should actually be named as isConnected. If the name is isConnected, there is no confusion. $\endgroup$ – kiner_shah Nov 24 at 6:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.