麻省理工学院：《算法导论》（英文版） Lecture 20 Prof erik demaine

Introduction to algorithms 6.046J/18,401J/SMA5503 Lecture 20 Prof erik demaine

Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 20 Prof. Erik Demaine

Disioint-set data structure (Union-Find) Problem: maintain a dynamic collection of pairwise-disjoint sets S=(S Each set S; has one element distinguished as the representative element, rep[sil lust support 3 operations MAKE-SET(): adds new set x to S with replx=x(for any x g si for all 1) UNION(X, y replaces sets Sy,S, with S U s in S for any x, y in distinct sets S, s FIND-SET(x): returns representative repISxi of set S containing element x c 2001 by erik D. Demaine Introduction to Agorithms Day33L20.2

© 2001 by Erik D. Demaine Introduction to Algorithms Day 33 L20.2 Disjoint-set data structure (Union-Find) Problem: Maintain a dynamic collection of pairwise-disjoint sets S = { S 1, S2, …, Sr }. Each set Si has one element distinguished as the representative element, rep [ Si ]. Must support 3 operations: • MAKE-SET (x ): adds new set { x } to S with rep[{ x}] = x (for any x ∉ Si for all i). • UNION (x, y ): replaces sets Sx, Sy with Sx ∪ Sy in S for any x, y in distinct sets Sx, Sy . • FIND-SET (x ): returns representative rep [ Sx ] of set Sx containing element x

Simple linked -list solution Store each set s; = 2…2k}asan( unordered doubly linked list. Define representative element reps,i to be the front of the list,x x十 re MAKE-SET(x) initializes x as a lone node. -o() FIND-SET(x) walks left in the list containing x until it reaches the front of the list ⊙(n) UNION(, y) concatenates the lists containing x and y, leaving rep. as FIND-setx -(n) c 2001 by erik D. Demaine Introduction to Agorithms Day33L20.3

© 2001 by Erik D. Demaine Introduction to Algorithms Day 33 L20.3 Simple linked-list solution Store each set Si = {x1, x2, …, xk} as an (unordered) doubly linked list. Define representative element rep[Si] to be the front of the list, x1. Si : x … 1 x2 xk rep[Si] • MAKE-SET(x) initializes x as a lone node. • FIND-SET(x) walks left in the list containing x until it reaches the front of the list. • UNION(x, y) concatenates the lists containing x and y, leaving rep. as FIND-SET[x]. – Θ(1) – Θ(n) – Θ(n)

Simple balanced -tree solution Store each set si=(x1, x2,.,xk as a balanced tree (ignoring keys). Define representative element replsii to be the root of the tree MAKE-SET(x) initializes x S={x12x2,x32x42x5} as a lone node. -O(1) rep[Six FIND-SET() walks up the tree containing x until it reaches the root. -o(g n UNION(, y) concatenates the trees containing x and changing rep o(g n) c 2001 by erik D. Demaine Introduction to Agorithms Day33L20.4

© 2001 by Erik D. Demaine Introduction to Algorithms Day 33 L20.4 Simple balanced-tree solution Store each set Si = {x1, x2, …, xk} as a balanced tree (ignoring keys). Define representative element rep[Si] to be the root of the tree. x1 x4 x3 x2 x5 • MAKE-SET(x) initializes x as a lone node. • FIND-SET(x) walks up the tree containing x until it reaches the root. • UNION(x, y) concatenates the trees containing x and y, changing rep. Si = {x1, x2, x3, x4, x5} rep[Si] – Θ(1) – Θ(lg n) – Θ(lg n)

Plan of attack We will build a simple disjoint-union data structure that, in an amortized sense performs significantly better than o(g n) per op, even better than o(glg n),o( Glg n), etc, but not quite O(1) To reach this goal, we will introduce two key tricks Each trick converts a trivial o(n) solution into a simple o(g n) amortized solution. Together, the two tricks yield a much better solution First trick arises in an augmented linked list Second trick arises in a tree structure c 2001 by erik D. Demaine Introduction to Agorithms Day33L20.5

© 2001 by Erik D. Demaine Introduction to Algorithms Day 33 L20.5 Plan of attack We will build a simple disjoint-union data structure that, in an amortized sense, performs significantly better than Θ(lg n) per op., even better than Θ(lg lg n), Θ(lg lg lg n), etc., but not quite Θ(1). To reach this goal, we will introduce two key tricks. Each trick converts a trivial Θ(n) solution into a simple Θ(lg n) amortized solution. Together, the two tricks yield a much better solution. First trick arises in an augmented linked list. Second trick arises in a tree structure

Augmented linked-list solution Store set S=x1,x2,.,xk as unordered doubly linked list. Define reps i to be front of list, x Each element x, also stores pointer rep[x, to reps rep S:[[…口 reps FiND-SEtX returns repx ⊙(1) UNION(x, y) concatenates the lists containing x and y, and updates the rep pointers for all elements in the list containing y ⊙(n) c 2001 by erik D. Demaine Introduction to Agorithms Day33L20.6

© 2001 by Erik D. Demaine Introduction to Algorithms Day 33 L20.6 Augmented linked-list solution Si : x … 1 x2 xk rep[Si] rep Store set Si = {x1, x2, …, xk} as unordered doubly linked list. Define rep[Si] to be front of list, x1. Each element xj also stores pointer rep[xj] to rep[Si]. • FIND-SET(x) returns rep[x]. • UNION(x, y) concatenates the lists containing x and y, and updates the rep pointers for all elements in the list containing y. – Θ(n) – Θ(1)

Example of augmented linked-list solution Each element x, stores pointer reply] to rep[si UNION(x, y) concatenates the lists containing x and y and updates the rep pointers for all elements in the list containing y reD rep P [十 reps, c 2001 by erik D. Demaine Introduction to Ago orns Day33L20.7

© 2001 by Erik D. Demaine Introduction to Algorithms Day 33 L20.7 Example of augmented linked-list solution Sx : x1 x2 rep[Sx] rep Each element xj stores pointer rep[xj] to rep[Si]. UNION(x, y) • concatenates the lists containing x and y, and • updates the rep pointers for all elements in the list containing y. Sy : y1 y2 y3 rep[Sy] rep

Example of augmented linked-list solution Each element x, stores pointer reply] to rep[si UNION(x, y) concatenates the lists containing x and y and updates the rep pointers for all elements in the list containing y reD 囗口s rep P 凹[ reps, c 2001 by erik D. Demaine Introduction to Ago orns Day33L20.8

© 2001 by Erik D. Demaine Introduction to Algorithms Day 33 L20.8 Example of augmented linked-list solution Sx ∪ Sy : x1 x2 rep[Sx] rep Each element xj stores pointer rep[xj] to rep[Si]. UNION(x, y) • concatenates the lists containing x and y, and • updates the rep pointers for all elements in the list containing y. y1 y2 y3 rep[Sy] rep

Example of augmented linked-list solution Each element x, stores pointer reply] to rep[si UNION(x, y) concatenates the lists containing x and y and updates the rep pointers for all elements in the list containing y reD 囗口s repS, 凹[[口 c 2001 by erik D. Demaine Introduction to Ago orns Day33L20.9

© 2001 by Erik D. Demaine Introduction to Algorithms Day 33 L20.9 Example of augmented linked-list solution Sx ∪ Sy : x1 x2 rep[Sx ∪ Sy] Each element xj stores pointer rep[xj] to rep[Si]. UNION(x, y) • concatenates the lists containing x and y, and • updates the rep pointers for all elements in the list containing y. y1 y2 y3 rep

Alternative concatenation UNION(X, y)could instead concatenate the lists containing y and x, and update the rep pointers for all elements in the list containing x rep :x十 rep reps s:[ reps, c 2001 by erik D. Demaine Introduction to Agorithms Day33L20.10

© 2001 by Erik D. Demaine Introduction to Algorithms Day 33 L20.10 Alternative concatenation Sx : x1 x2 rep[Sy] UNION(x, y) could instead • concatenate the lists containing y and x, and • update the rep pointers for all elements in the list containing x. y1 y2 y3 rep rep[Sx] rep Sy :