To implement operations like make set, union, and find set on disjoint sets, two

Question

To implement operations like make set, union, and find set on disjoint sets, two data structures: linked lists and directed forests, have been introduced for representing the disjoint sets. (i) In the linked list representation, there is a heuristic for performing the union operation of two linked lists into one, what is the name of this heuristic? Explain the heuristic briefly. (ii) In the use of the directed forest data structure to represent the disjoint sets, the two heuristics path compression and union by rank are introduced. 1. Explain the two mentioned heuristics briefly.2. • Show that a converted tree with the root rank k (k 0) in the directed forest contains at least 2 k nodes.

Explanation / Answer

i) To perform the union operation of two linked lists in one, the heuristic is weighted union heuristic.

Weighted union heuristic is an heuristic that does make an algorithm more efficient. Let’s say that the representative of a set contains information about how many objects (elements) are in that set as well. The optimization is to always append the smaller list onto the longer and, in case of ties, append arbitrarily. This will bring the complexity of the algorithm to O(M + NlogN) where M is the number of operations.

These are the three algorithms for MAKE-SET, FIND-SET and UNION, using linked list representation and weighted union heuristic.

ii) The two heuristics are : Union by rank and path compression.

1) The idea of union by rank is to make the root of the tree with fewer nodes point to the root of the tree with more nodes. Rather than explicitly keeping track of the size of the subtree rooted at each node, for each node we maintain a rank that approximates the logarithm of the subtree size and is also an upper bound on the height of the node.Time complexity: O(mlogn), assuming that there are m union operations.

Path compression is quite simple and very effective. We use this approach during FIND-SET operations to make each node on the path point directly to the root. Path compression does not change any ranks.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.