𝟐𝟒𝟔𝟕 𝟏𝟑𝟖𝟗𝟎𝟓
Lecture 12: Weighted Quick-Union
CSC 226: Algorithms and Data Structures II Quinton Quick-Union
• Modify quick-union to avoid tall trees
Copyright By PowCoder代写 加微信 powcoder
• Keep track of the size of each tree (number of objects)
• Balance by linking root of smaller tree to root of larger tree
Quick-Union 𝑼𝒏𝒊𝒐𝒏(𝒖, 𝒗):
Causes tall tree
More balanced
Weighted 𝑼𝒏𝒊𝒐𝒏(𝒖, 𝒗):
𝒗 or 𝒖 Always balanced
Weighted Quick-Union
• Modify quick-union to avoid tall trees
• Keep track of the size of each tree (number of objects)
• Balance by linking root of smaller tree to root of larger tree
𝒊𝒅[] 𝟎 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 𝟕 𝟖 𝟗
0123456789
𝟎𝟏𝟐𝟑𝟒𝟓𝟔𝟕𝟖𝟗
Weighted Quick-Union
• Modify quick-union to avoid tall trees
• Keep track of the size of each tree (number of objects)
• Balance by linking root of smaller tree to root of larger tree
𝑼𝒏𝒊𝒐𝒏(𝟒, 𝟑):
𝒊𝒅[] 𝟎 𝟏 𝟐 𝟒 𝟒 𝟓 𝟔 𝟕 𝟖 𝟗
0123456789
𝟎𝟏𝟐 𝟒𝟓𝟔𝟕𝟖𝟗 𝟑
Weighted Quick-Union
• Modify quick-union to avoid tall trees
• Keep track of the size of each tree (number of objects)
• Balance by linking root of smaller tree to root of larger tree
𝑼𝒏𝒊𝒐𝒏(𝟑, 𝟖):
𝒊𝒅[] 𝟎 𝟏 𝟐 𝟒 𝟒 𝟓 𝟔 𝟕 𝟒 𝟗
0123456789
𝟎𝟏𝟐𝟒𝟓𝟔𝟕 𝟗 𝟑𝟖
Weighted Quick-Union
• Modify quick-union to avoid tall trees
• Keep track of the size of each tree (number of objects)
• Balance by linking root of smaller tree to root of larger tree
𝑼𝒏𝒊𝒐𝒏(𝟔, 𝟓):
𝒊𝒅[] 𝟎 𝟏 𝟐 𝟒 𝟒 𝟔 𝟔 𝟕 𝟒 𝟗
0123456789
𝟎𝟏𝟐𝟒𝟔𝟕𝟗 𝟑𝟖𝟓
Weighted Quick-Union
• Modify quick-union to avoid tall trees
• Keep track of the size of each tree (number of objects)
• Balance by linking root of smaller tree to root of larger tree
𝑼𝒏𝒊𝒐𝒏(𝟗, 𝟒):
𝒊𝒅[] 𝟎 𝟏 𝟐 𝟒 𝟒 𝟔 𝟔 𝟕 𝟒 𝟒
0123456789
𝟎𝟏𝟐𝟒𝟔𝟕 𝟑𝟖𝟗 𝟓
Weighted Quick-Union
• Modify quick-union to avoid tall trees
• Keep track of the size of each tree (number of objects)
• Balance by linking root of smaller tree to root of larger tree
𝑼𝒏𝒊𝒐𝒏(𝟐, 𝟏):
𝒊𝒅[] 𝟎 𝟐 𝟐 𝟒 𝟒 𝟔 𝟔 𝟕 𝟒 𝟒
0123456789
𝟎𝟐𝟒𝟔𝟕 𝟏𝟑𝟖𝟗𝟓
Weighted Quick-Union
• Modify quick-union to avoid tall trees
• Keep track of the size of each tree (number of objects)
• Balance by linking root of smaller tree to root of larger tree
𝑼𝒏𝒊𝒐𝒏(𝟓, 𝟎):
𝒊𝒅[] 𝟔 𝟐 𝟐 𝟒 𝟒 𝟔 𝟔 𝟕 𝟒 𝟒
0123456789
𝟐𝟒𝟔𝟕 𝟏𝟑𝟖𝟗𝟎𝟓
Weighted Quick-Union
• Modify quick-union to avoid tall trees
• Keep track of the size of each tree (number of objects)
• Balance by linking root of smaller tree to root of larger tree
𝑼𝒏𝒊𝒐𝒏(𝟕, 𝟐):
𝒊𝒅[] 𝟔 𝟐 𝟐 𝟒 𝟒 𝟔 𝟔 𝟐 𝟒 𝟒
0123456789
𝟐𝟒𝟔 𝟏𝟕𝟑𝟖𝟗𝟎𝟓
Weighted Quick-Union
• Modify quick-union to avoid tall trees
• Keep track of the size of each tree (number of objects)
• Balance by linking root of smaller tree to root of larger tree
𝑼𝒏𝒊𝒐𝒏(𝟔, 𝟏):
𝒊𝒅[] 𝟔 𝟐 𝟔 𝟒 𝟒 𝟔 𝟔 𝟐 𝟒 𝟒
0123456789
Weighted Quick-Union
• Modify quick-union to avoid tall trees
• Keep track of the size of each tree (number of objects)
• Balance by linking root of smaller tree to root of larger tree
𝑼𝒏𝒊𝒐𝒏(𝟕, 𝟑):
𝒊𝒅[] 𝟔 𝟐 𝟔 𝟒 𝟔 𝟔 𝟔 𝟐 𝟒 𝟒
0123456789
Weighted Quick-Union
Data structure implementation:
• Same as quick-union, but maintain an additional array 𝒔𝒊𝒛𝒆[𝒓] to keep track of the number of objects in the tree rooted at 𝒓.
𝒊𝒅[] 𝟔 𝟐 𝟔 𝟒 𝟔 𝟔 𝟔 𝟐 𝟒 𝟒
0123456789
𝑭𝒊𝒏𝒅(𝒆): Identical to quick-union
𝑼𝒏𝒊𝒐𝒏(𝒖, 𝒗): Modify quick-union to:
• Linkrootofsmallertreetorootoflargertree
• Update𝒔𝒊𝒛𝒆[𝒓]ofroot𝒓ofmergedtree
• Note: we only update the 𝒔𝒊𝒛𝒆[𝒓] of the new root 𝒓
Weighted Quick-Union Time Complexity
• Find:Timeproportionaltodepthofelement𝒙itstree • Union: 𝑶 𝟏 after finding the root
Proposition: The depth of any node 𝒙 is 𝑶 𝐥𝐨𝐠 𝒏 Proof: Let 𝒙 be in tree 𝑻𝟏.
What causes the depth of 𝒙 to increase?
Depth 𝒅 + 𝟏
The depth of 𝒙 increases by 1 only when 𝑻𝟏 is merged into another tree 𝑻𝟐. Since 𝑻𝟏 is merged into 𝑻𝟐, that means 𝑻𝟐 ≥ 𝑻𝟏 .
So, the size of the new tree 𝑻𝟏 ∪ 𝑻𝟐 containing 𝒙 is at least double the size of 𝑻𝟏.
1 2 4 8 16
With 𝒏 total elements, the tree containing 𝒙 can double in size at most 𝐥𝐨𝐠𝟐(𝒏) times. Hence, the depth of 𝒙 is at most 𝐥𝐨𝐠𝟐 𝒏 .
Therefore, the depth of any node 𝒙 is 𝑶 𝐥𝐨𝐠 𝒏 .
Weighted Quick-Union Time Complexity
𝒊𝒅[] 𝟔 𝟐 𝟔 𝟒 𝟔 𝟔 𝟔 𝟐 𝟒 𝟒 𝟒 𝟎 𝟐 𝟓
0123456789
• Initialization: 𝑶 𝒏
• Union: 𝑶 𝐥𝐨𝐠 𝒏 // includes cost of finding roots • Find: 𝑶 𝐥𝐨𝐠 𝒏
• Same Component:𝑶 𝐥𝐨𝐠 𝒏
Reducing height of trees results in better running time of find, which also improves union. We can improve time even more by flattening the trees further.
Weighted Quick-Union with Path Compression
After computing the root of an element 𝒙, set the 𝒊𝒅[] of each examined node to point to that root 𝟎
Weighted Quick-Union with Path Compression
After computing the root of an element 𝒙, set the 𝒊𝒅[] of each examined node to point to that root
Weighted Quick-Union with Path Compression
After computing the root of an element 𝒙, set the 𝒊𝒅[] of each examined node to point to that root
Weighted Quick-Union with Path Compression
After computing the root of an element 𝒙, set the 𝒊𝒅[] of each examined node to point to that root
𝟗𝟔𝟑𝟏𝟐 𝟏𝟏𝟏𝟐𝟖 𝟕𝟒𝟓
𝑭𝒊𝒏𝒅() has the effect of compressing the tree
Path Compression Implementation
Two-pass implementation: After finding the root, perform a second pass and set 𝒊𝒅[] of each examined node to the root.
𝟗𝟔𝟑𝟏𝟐 𝟏𝟏𝟏𝟐𝟖 𝟕𝟒𝟓
One-pass variant (path halving): On find() path the root, make every node point to its grandparent • 𝒊𝒅𝒊 =𝒊𝒅𝒊𝒅𝒊
Path Compression Implementation
One-pass variant (path halving): On find() path the root, make every node point to its grandparent • 𝒊𝒅𝒊 =𝒊𝒅𝒊𝒅𝒊
Path Compression Implementation
One-pass variant (path halving): On find() path the root, make every node point to its grandparent • 𝒊𝒅𝒊 =𝒊𝒅𝒊𝒅𝒊
𝟏𝟏 𝟏𝟐 𝟖 𝟏𝟎
(Extra) Weighted QU + PC: Amortized Analysis
Proposition [Hopcroft-Ulman, Tarjan]: Starting from an empty data structure, a sequence of 𝒎 union- find operations on 𝒏 objects takes 𝑶 𝒏 + 𝒎 𝐥𝐨𝐠∗ 𝒏
𝐥𝐨𝐠∗ 𝒏 definition: Number of times the log function is iteratively applied to 𝒏 before the result is ≤ 𝟏
• 𝐥𝐨𝐠∗ 𝟐𝟔𝟓𝟓𝟑𝟔 = 𝟓
𝟏𝟔 =𝟑 𝟔𝟓𝟓𝟑𝟔 =𝟒
Summary analysis of 𝒎 union-find operations on a set of 𝒏 objects
(i.e. initializing the data structure then doing 𝒎 𝒖𝒏𝒊𝒐𝒏() and 𝒇𝒊𝒏𝒅() operations)
• Quick-find:
• Quick-union:
• WeightedQU:
• QU+pathcompression:
• Weighted QU + path compression:
𝑶 𝒏+𝒎𝐥𝐨𝐠 𝒏 𝑶 𝒏+𝒎𝐥𝐨𝐠 𝒏 𝑶 𝒏 + 𝒎 𝐥𝐨𝐠∗ 𝒏
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com