Nếu bạn đã từng thực thi thuật toán Kruskal tìm cây khung nhỏ nhất, chắc bạn sẽ biết cấu trúc union-find. Đó là một trong số rất nhiều ứng dụng của cấu trúc này. Trong phần này mình trình bày cấu trúc đó góc độ một cấu trúc dữ liệu để lưu trữ các tập hợp rời nhau (disjoint sets). Do đó, cấu trúc này còn gọi là disjoint-set data structure. Bài toán của chúng ta như sau:
- MakeSet($x$): Tạo tập hợp $\{x\}$.
- Find($x$): Trả lại id của tập hợp chứa $x$.
- Union($x,y$): Thay thế hai tập hợp $A,B$ lần lượt chứa $x$ và $y$ bằng tập hợp $A \cup B$. Ở đây ta giả sử phép Union luôn gộp 2 phần tử thuộc hai tập khác nhau.
Hãy thiết kế một cấu trúc dữ liệu cho thuật toán $A$ sao cho các thao tác này được thực hiện một cách hiệu quả nhất.
Cấu trúc dựa trên danh sách
Trong cấu trúc này, mỗi tập hợp được lưu trữ bởi môt danh sách liên kết, và mỗi phần tử của danh sách sẽ có một con trỏ head chỉ đến đầu của danh sách (có thể coi là id của danh sách vì mỗi phần tử chỉ xuất hiện trong tối đa 1 danh sách).
Các thao tác MakeSet($x$) và Find($x$) có thể được thực hiện trong thời gian $O(1)$ như sau:
MakeSet($x$):
$\mathrm{head}(x) \leftarrow x$
Find($x$):
return $\mathrm{head}(x)$
Với cấu trúc lưu trữ này, ta có thể thực hiện thao tác gộp hai tập $A,B$ với chiều dài tương ứng $ |A|, |B| $ trong thời gian $O(|A| + |B|)$ như sau:
- Nối danh sách $B$ và cuối danh sách $A$ bằng cách duyệt từ đầu danh sách $A$ đến phần tử cuối cùng $x$ rồi đưa con trỏ next của $x$ trỏ đến đầu danh sách $B$.
- Đưa con trỏ head của các phần tử trong $B$ trỏ đến đầu của danh sách $A$
Ta có thể áp dụng một vài kĩ thuật như sau để cải tiến ý tưởng của thuật toán ở trên:
- Với mỗi danh sách lưu thêm thông tin kích thước size của danh sách và đổi vai trò $A, B$ trong thuật toán trên nếu $|A| < |B|$.
- Phần tử đầu của mỗi danh sách sẽ có thêm một con trỏ chỉ end đến cuối danh sách. Do đó ta có thể tiết kiệm được bước duyệt danh sách.
Do đó:
Ở đây chú ý là chúng ta phải thay đổi thủ tục MakeSet($x$) khởi tạo thông tin size và contrỏ end (chi tiết coi như bài tập). Giả mã của thao tác Union như sau:
Union($x,y$):
$\bar{x} \leftarrow $ Find($x$) [[head of $A$]]
$\bar{y}\leftarrow $ Find($y$) [[head of $B$]]
if $\mathrm{size}(\bar{x})$ < $\mathrm{size}(\bar{y})$
$\mathrm{swap}(\bar{x}, \bar{y})$
$\mathrm{size}(\bar{x}) \leftarrow \mathrm{size}(\bar{x}) + \mathrm{size}(\bar{y})$
$\hat{x} \leftarrow \mathrm{end}(\bar{x})$ [[the end of the longer list]]
$\mathrm{next}(\hat{x}) \leftarrow \bar{y}$
$\mathrm{ptr}\leftarrow \hat{x}$
while $\mathrm{next}(\mathrm{ptr}) \not= \mathrm{NULL}$
$\mathrm{ptr}\leftarrow \mathrm{next}(\mathrm{ptr})$
$\mathrm{head}(\mathrm{ptr}) \leftarrow \bar{x}$
$\mathrm{head}(\mathrm{ptr}) \leftarrow \bar{x}$
$\mathrm{end}(\bar{x}) \leftarrow \mathrm{ptr}$
Thao tác union được minh họa trong hình dưới đây:
Trong trường hợp xấu nhất, ta sẽ mất thời gian $O(n)$ để gộp hai danh sách có kích thước cỡ $O(n)$. Tuy nhiên, những trường hợp như vậy sẽ "không thường xuyên" xảy ra vì sau khi gộp ta thu được danh sách kích thước $|A| + |B|$. Nếu phân tích kĩ hơn ta sẽ thấy trung bình mỗi thao tác Union($x,y$) chỉ tốn cỡ $O(\log n)$.
Chứng minh: Dễ thấy $k$ bước union sẽ thao tác trên tập $S \subseteq X$ có kích thước $|S| \leq 2k$ vì mỗi thao tác union chỉ thao tác trên tối đa $2$ phần tử mới. Xét một phần tử $x \in S$, ta sẽ phân tích xem bao nhiêu lần con trỏ head của $x$ được cập nhật. Từ bổ đề 1, mỗi lần cập nhật con trỏ head, kích thước của tập hợp chứa $x$ tăng lên ít nhất 2 lần. Do đó, con trỏ head của $x$ được cập nhật tối đa $\log 2k = O(\log k)$ lần. Từ đó, ta thu được định lý 1.
Từ định lý 1, ta thu được hệ quả sau:
Do đó, có thể coi thời gian "khấu trừ" (amortized time) của mỗi thao tác Union là $O(\log n)$.
Cấu trúc cây
Trong cấu trúc cây, mỗi tập hợp sẽ được biểu diễn bởi một cây và mỗi nút của cây có một con trỏ chỉ tới một nút cha (parent -- người viết không có ý phân biệt cha/mẹ, chỉ là thấy nghe cha "xuôi hơn"). Id của tập hợp là id của nút gốc của cây. Ngoài ra, gốc của mỗi cây lưu thông tin depth là chiều cao của cây biểu diễn tập hiện tại. Trong cấu trúc cây, thao tác MakeSet vẫn có thời gian hằng số $O(1)$, tuy nhiên thao tác Find sẽ không còn là hằng số nữa. Sự linh động đó cũng dẫn đến nhiều phương pháp cải tiến cấu trúc này. Trước hết mình trình bày cấu trúc cây đơn giản, là cơ sở cho các cải tiến sau này.
Cấu trúc cây đơn giản
Hai thao tác MakeSet và Find trong cấu trúc cây như sau:
Find($x$):
while parent($x$) $\not= x$
$x\leftarrow$ parent$(x)$
return $x$
Để phép Find được hiệu qủa, chúng ta thiết kế sao cho chiều cao của cây càng nhỏ càng tốt. Mặt khác chúng ta phải duy trì cấu trúc cây sao cho phép Union thực hiện được hiệu qủa. Trong cấu trúc cây, phép Union sẽ gộp cây có chiều cao nhỏ vào cây có chiều cao lớn hơn (gốc của cây nhỏ hơn sẽ trở thành nut con của gốc của cây lớn hơn). Khác với cấu trúc danh sách, trong cấu trúc cây, chúng ta không cần phải thay đổi con trỏ của các nút của cây khi gộp ngoại trừ nút gốc, do đó, phép Union có thể được thực hiện nhanh hơn. Giả mã như sau:
Union($x,y$):
$\bar{x} \leftarrow $ Find($x$) [[the root of $A$]]
$\bar{y}\leftarrow $ Find($y$) [[the root of $B$]]
if depth($\bar{x}$) $ > $ depth($\bar{y}$)
parent($\bar{y}$) $\leftarrow \bar{x}$
else
parent($\bar{x}$) $ \leftarrow \bar{y}$
if depth($\bar{x}$) $=$ depth($\bar{y}$)
depth($\bar{y}$) $\leftarrow $ depth($\bar{y}$) $+1$
Chứng minh: Gọi $x$ là cây có chiều cao lớn nhất $\mathrm{depth}(x)$. Có thể chứng minh được bằng quy nạp số lượng nút trong cây có gốc $x$ ít nhất là $2^{\mathrm{depth}(x)}$. Do đó $\mathrm{depth}(x) \leq \log n$.
Cây kết hợp nén đường đi
Ý tưởng cải thiện cấu trúc cây cơ bản như sau: mỗi lần thực hiện thao tác Find($x$), ta kết hợp với cập nhật con trỏ của các nút trên đường đi từ nút $x$ tới nút gốc $r$ của cây chứa $x$ để trỏ tới nút gốc.
Không khó để nhận thấy nếu thao tác Find($x$) mất thời gian $O(T(n))$ thì việc thêm thao tác cập nhật con trỏ trên đường đi (còn gọi là nén đường đi -- path compression) mất thời gian $O(2T(n)) = O(T(n))$. Do đó, về mặt tiệm cận, thời gian của thao tác Find($x$) không thay đổi.
Find($x$):
if parent($x$) $\not= x$
$\mathrm{parent}(x) \leftarrow $ Find($\mathrm{parent}(x)$)
return $\mathrm{parent}(x)$
Do kết hợp với nén đường đi mỗi lần tìm kiếm, thông tin depth của nút gốc sẽ bị thay đổi. Cập nhật thông tin này rất tốn kém. Do đó, ta có thể thay đổi một chút, thay vì gộp cây theo độ sâu (depth), ta sẽ gộp cây theo hạng (rank). Thủ tục MakeSet và Union vẫn tương tự như trường hợp cây cơ bản.
Union($x,y$):
$\bar{x} \leftarrow $ Find($x$) [[the root of $A$]]
$\bar{y}\leftarrow $ Find($y$) [[the root of $B$]]
if $\mathrm{rank}(\bar{x}) > \mathrm{rank}(\bar{y})$
$\mathrm{parent}(\bar{y}) \leftarrow \bar{x}$
else
$\mathrm{parent}(\bar{x}) \leftarrow \bar{y}$
if $\mathrm{rank}(\bar{x}) = \mathrm{rank}(\bar{y})$
$\mathrm{rank}(\bar{y}) \leftarrow \mathrm{rank}(\bar{y}) +1$
Một số tính chất của hạng chúng ta có thể liệt kê ra như sau:
- Nếu $x$ không phải là nút gốc, hạng của $x$ nhỏ hơn hạng của nút cha.
- Hạng của $x$ chỉ thay đổi khi $x$ là nút gốc. Nếu một nút không còn là gốc nữa, hạng cuả nó sẽ không bao giờ thay đổi.
- Khi $\mathrm{parent}(x)$ thay đổi, cha mới của $x$ có hạng lớn hơn cha cũ của $x$.
- Có tối đa $\frac{n}{2^r}$ nút có hạng $\geq r$.
Tính chất cuối cùng không dễ để nhận thấy, tuy nhiên chúng ta có thể lập luận như sau: để ý thấy nếu một nút thay đổi hạng từ $r-1$ lên $r$ (trường hợp này xảy ra khi gộp hai cây có gốc có cùng hạng $r-1$), cây mới có ít nhất $2^r$ nút. Theo tính chất 2, hạng của các nút không phải là gốc sẽ không bao giờ thay đổi, ta có thể gán cho mỗi nút $x$ hạng $r$ một tập hợp $S_x$ chứa $x$ có kích thước $|S_x| \geq 2^r$. Do với hai nút $x,y$ có cùng hạng $r$, $S_x \cap S_y = \emptyset$. Do đó, có tối đa $\frac{n}{2^r}$ nút có hạng $\geq r$.
Ta sẽ phân tích thời gian tính toán của thao tác Find vì thao tác Union tốn thời gian bằng 2 thao tác Find cộng với một hằng số. Trước hết ta định nghĩa hàm $\log^* n$.
$\log^* n = \begin{cases}1, & \mbox{if } n \leq 2\\1 + \log^*(\log n) , & \mbox{otherwise}\end{cases}$
Hàm $\log^* n$ tăng cực chậm, với $n = 2^{2^{16}} = 2^{65536}\sim 2\times 10^{19728}$, $\log^* n = 5$, do đó, có thể coi thực tế $\log^* n$ nhỏ hơn hoặc bằng $5$ (cả vũ trụ mới có cỡ ~$10^{85}$ hạt cơ bản).
Một hàm tăng chậm khác dùng trong phân tích union-find là hàm Ackerman ngược, kí hiệu $\alpha(n)$. Hàm này còn chậm hơn rất nhiều so với hàm $\log^* n$. Tarjan [4] chứng minh rằng mỗi thao tác find trong cấu trúc cây kết hợp nén đường đi có thời gian khấu trừ $\alpha(n)$. Trong bài này, mình chứng minh kết quả yếu hơn:
Chứng minh: Ta có thể tính thời gian cho mỗi thao tác Find($x$) bằng cách đếm "chi phí" như sau:
- Nếu $x$ là gốc, ta sẽ lấy từ $x$ $1$ đồng cho thao tác Find($x$).
- Nếu $x$ là con của một nút gốc, ta sẽ lấy từ $x$ $2$ đồng cho thao tác Find($x$).
- Cứ như vậy, trong quá trình thực hiện Find($x$), ta sẽ lấy từ $x$ $1$ đồng cho mỗi lần đi từ một nút đến một nút cha.
Cuối cùng, $x$ phải trả chi phí là số tiền mà nó nợ. Nếu $x$ ở độ sâu càng lớn, chi phí $x$ phải trả cuối cùng càng nhiều. Tuy nhiên, sau khi đã thực hiện thao tác find đối với $x$ và nén đường đi, các thao tác tìm kiếm các nút trên đường đi từ $x$ tới nút gốc sau đó sẽ rẻ hơn rất nhiều. Do đó, các nút trên đường đi đó được hưởng lợi từ $x$. Để cho công bằng giữa các nút, chúng ta sẽ tìm cách nào đó để "khấu trừ" chi phí khi thực hiện Find($x$), hay nói cách khác, các nút trên đường đi từ $x$ tới gốc cũng phải trả bớt tiền mà $x$ nợ.
Trước hết ta sẽ phân các nút thành các nhóm như sau:
- Nhóm $0$ gồm các nút có hạng $0$
- Nhóm $1$ gồm các nút có hạng $1$
- Nhóm $2$ gồm các nút có hạng $2$ đến $2^2-1$
- Nhóm $3$ gồm các nút có hạng $2^2$ đến $2^{2^2}-1$
- $\ldots$
- Nhóm $i$ gồm các nút có hạng $2\uparrow\uparrow (i-2)$ đến $2\uparrow\uparrow (i-1)-1$
Ở đây kí hiệu $2\uparrow\uparrow i = 2^{2^{\cdot^{\cdot^{2}}}}$, dấu mũ lặp lại $i$ lần. Tóm lại mỗi nhóm có hạng từ $r$ tới $2^r-1$. Một vài điểm quan trọng ở đây là:
- Có tất cả $\log^* n$ nhóm.
- Nhóm có hạng từ $r$ tới $2^r-1$ sẽ có số phần tử tối đa là:
$\sum_{i=r}^{2^r-1}\frac{n}{2^i} \leq \frac{2n}{2^{r}} $
Xét một đường đi $P$ từ $x$ tới nút gốc trong thao tác Find($x$). Giả sử $P$ đi qua hai nút $u$ và $v$ trong đó nút $v$ là cha của nút $u$. Nếu $u$ và $v$ nằm trong cùng một nhóm, ta lấy $1$ đồng từ $u$ thay vì từ $x$ (vì $u$ được hưởng lợi). Nếu $v$ nằm trong nhóm cao hơn (là nhóm có số thứ tự cao hơn), ta sẽ lấy $1$ đồng từ $x$. Do đó:
Nhận xét: $x$ chỉ phải trả $\log^* n$ đồng vì chúng ta chỉ có $\log^* n$ nhóm khác nhau.
Bây giờ sẽ là phần khó nhất, đó là trung bình mỗi nút $u$ như trên phải trả bao nhiêu đồng? Thứ nhất, nút $u$ sẽ không bao giờ thay đổi hạng, theo tính chất 2 của hạng. Thứ hai, mỗi lần nút $u$ trả bớt $1$ đồng cho một nút nào đó, hạng của cha của $u$ tăng ít nhất lên 1, và cha của $u$ phải nằm trong cùng một nhóm với $u$. Do đó, nếu hạng của cha của $u$ tăng đến mức của nhóm tiếp theo, $u$ sẽ không bao giờ phải trả tiền cho bất kì một nút nào khác. Như vậy, $u$ phải trả tối đa số tiền là phạm vi của hạng trong nhóm chứa $u$ ( là $2^r-r$ nếu $u$ trong nhóm có hạng bắt đầu từ $r$ đến $2^r-1$).
Nhóm chứa $u$ có kích thước là $\frac{2n}{2^r}$, do đó, tổng số tiền mà tất cả các nút trong nhóm này phải "trả hộ" nút khác là:
$(2^r-r)\frac{2n}{2^r} \leq 2n$
Do đó, tổng số tiền "trả hộ" của tất cả các nút là $2n\log^* n$ vì số nhóm là $\log^* n$.
Tổng kết lại như sau: nếu ta có $m$ thao tác Find($x$), số tiền tất cả các nút phải trả cuối cùng là $O(m\log^* n + n \log^* n) = O((m+n)\log^* n)$. Trong hầu hết các thuật toán $m\sim \Omega(n)$, do đó thời gian khấu trừ cho mỗi thao tác Find là $O(\log^* n)$.
Thực thi
Với cấu trúc danh sách liên kết, cách thực thi hiệu qủa có lẽ cũng là sử dụng danh sách liên kết. Tuy nhiên với cấu trúc cây, chúng ta không nhất thiết phải sử dụng cây để thực thi. Phần này mình sẽ giới thiệu phương pháp thực thi bằng mảng (array). Ta sử dụng hai mảng:
- Mảng $P[1,2,\ldots,n]$ để lưu trữ chỉ số của nút cha, i.e, $P[i] = j$ có nghĩa là cha của phần tử $X[i]$ sẽ là $X[j]$.
- Mảng $R[1,2,\ldots,n]$ để lưu trữ hạng (rank) của mỗi nút,i.e, $R[i] = k$ nghĩa là hạng của $X[i]$ là $k$.
Các thao tác cơ bản như sau:
Find($x$):
if $P[x] \not= x$
$P[x] \leftarrow $ Find($P[x]$)
return $P[x]$
Union($x,y$):
$\bar{x} \leftarrow $ Find($x$) [[the root of $A$]]
$\bar{y}\leftarrow $ Find($y$) [[the root of $B$]]
if $R[\bar{x}] > R[\bar{y}]$
$P[\bar{y}] \leftarrow \bar{x}$
else
$P[\bar{x}] \leftarrow \bar{y}$
if $R[\bar{x}] = R[\bar{y}]$
$R[\bar{y}] \leftarrow R[\bar{y}] +1$
Ứng dụng
Union-Find có rất nhiều ứng dụng mà nổi tiếng là trong thực thi thuật toán Kruskal tìm cây khung nhỏ nhất. Trong phần này mình sẽ giới thiệu ứng dụng của Union-Find trong việc thiết kế giải thuật $O(n\alpha(n))$ cho bài toán lập lịch có thời hạn đã giới thiệu trọng bài thuật toán tham lam. Chi tiết xem thêm tại bài trước. Ở đây mình nhắc lại đề bài và thuật toán tham lam $O(n^2)$:
Giải thuật $O(n^2)$:
sort jobs by $\uparrow$ order of profit.
permute $P,D$ to match indices.
$X[1,2,\ldots,n] \leftarrow \{0,0,\ldots, 0\}$
for $i \leftarrow 1$ to $n$
$j \leftarrow D[i]$
while $(X[j]\not= 0)$ and $(j \geq 1)$
$j \leftarrow j-1$
if $j \not= 0$
$X[j] \leftarrow i$
Trong thuật toán trên, thời gian để tìm một vị trí để chèn một tác vụ mới mất cỡ $O(n)$. Bằng Union-Find, sử dụng cấu trúc cây kết hợp nén đương đi, chúng ta có thể giảm thời gian này xuống $\alpha(n)$, do đó, thuật toán sẽ có tổng thời gian là $O(n\alpha(n))$ (nếu không tính bước sắp xếp mất $n\log n$).
Giả sử thời điểm hiện tại ta có mảng $X[1,2,\ldots,n]$ là mảng lưu trữ lịch trình của các tác vụ chúng ta đã được vào lời giải tối ưu trong các bước trước. Mỗi tập hợp của chúng ta sẽ biểu diễn một dãy liên tục và tối đại (maximal) các phần tử khác 0 $X[i,i+1,\ldots,j]$ của mảng $X[1,2,\ldots,n]$. Nói cách khác, với mỗi tập hợp chứa các phần tử $X[i,i+1,\ldots,j]$, ta luôn đảm bảo điều kiện:
$X[i-1] = X[j+1] = 0 \qquad (1)$
Ngoài ra, gốc của mỗi tập hợp sẽ lưu trữ số $i-1$, là vị trí trái nhất (left-most) còn trống của dãy liên tục này. Để kiểm tra xem tác vụ $j$ với thời hạn $D[j]$ có thể chèn vào lịch trình $X[1,2,\ldots,n]$ hiện tại được không, ta làm như sau:
- Nếu $X[D[j]] = 0$, ta thêm tác vụ $j$ và vị trí X[D[j]] và gọi MakeSet($D[j]$). Nếu $X[D[j-1]-1] \not= 0$, để đảm bảo điều kiện $(1)$, ta gọi Union($D[j], D[j]-1$). Nếu $X[D[j-1]+1] \not= 0$,để đảm bảo điều kiện $(1)$, ta gọi Union($D[j], D[j]+1$)
- Nếu $X[D[j]] \not= 0$, ta gọi Find($D[j]$) để tìm tập hợp chứa $D[j]$ và từ đó tìm được ví trí left-most của dãy, i.e, giả sử là $k$. Ta chèn $j$ vào vị trí $X[k]$. Nếu $X[k-1] \not= 0$, để đảm bảo điều kiện $(1)$, ta gọi Union($k-1, D[j]$).
Chi tiết giả mã như sau:
sort jobs by $\uparrow$ order of profit.
permute $P,D$ to match indices.
$X[1,2,\ldots,n] \leftarrow \{0,0,\ldots, 0\}$
for $i \leftarrow 1$ to $n$
$j \leftarrow D[i]$
if $X[j] = 0 $
$X[j] \leftarrow i$
MakeSet($j$)
if $X[j+1] \not=0 $
Union($j, j+1$)
if $X[j-1] \not=0 $
Union($j-1, j$)
else
$k \leftarrow Lm[$ Find($j$)$]$ [[the left-most empty slot]]
if $k \not= 0$
$X[k] \leftarrow i$
MakeSet($k$)
Union($k,j$)
if $X[k-1] \not= 0$
Union($k-1, k$)
$P[x] \leftarrow x$
$R[x] \leftarrow 0$
$Lm[x] \leftarrow x-1$ [[the left-most supposed empty slot]]
Union($x,y$):
$\bar{x} \leftarrow $ Find($x$) [[the root of $A$]]
$\bar{y}\leftarrow $ Find($y$) [[the root of $B$]]
if $R[\bar{x}] > R[\bar{y}]$
$P[\bar{y}] \leftarrow \bar{x}$
else
$P[\bar{x}] \leftarrow \bar{y}$
$Lm[\bar{y}]\leftarrow Lm[\bar{x}]$
if $R[\bar{x}] = R[\bar{y}]$
$R[\bar{y}] \leftarrow R[\bar{y}] +1$
Code bằng C của giả mã:
#define MAX 1000000
#define INFTY 100000000
typedef struct {
int id;
int d;
int p;
} job;
job A[MAX];
int X[MAX];
int P[MAX], R[MAX], Lm[MAX];
long long union_find_scheduling(int n){
qsort(A, n, sizeof(*A), compare_profit); // sort jobs by increasing order of profit
memset(X, -1, sizeof(X)); // set everything to -1
memset(Lm, 0, sizeof(Lm));// set everything to 0
int i = 0, j = 0;
for(i = 0; i < n; i++){
j = A[i].d;
if(X[j] == -1){
X[j] = i;
makeSet(j);
if(X[j-1] != -1){
uniOn(j-1,j); // be careful the order
}
if(X[j+1] != -1){
uniOn(j,j+1);
}
} else {
int k = Lm[find(j)];
if(k != 0){
X[k] = i;
makeSet(k);
uniOn(k, j);
if(X[k-1] != -1){
uniOn(k-1,k);
}
}
}
}
long long total = 0;
for(i = 1; i <= n; i++){
if(X[i] != - 1){
total += (long long) A[X[i]].p;
}
}
return total;
}
void makeSet(int x){
P[x] = x;
R[x] = 0;
Lm[x] = x-1;
}
int find(int x){
if( P[x] != x){
P[x] = find(P[x]);
}
return P[x];
}
void uniOn(int x, int y){
int a = find(x);
int b = find(y);
if(R[a] > R[b]){
P[b] = a;
} else {
P[a] = b;
Lm[b] = Lm[a];
if( R[a] == R[b]){
R[b] ++;
}
}
}
Thủ tục Find($x$) không thay đổi so với ở trên. Mảng $Lm$ là mảng lưu trữ phần tử trái nhất còn trống của một tập. Một điểm chú ý là thứ tự của $x$ và $y$ trong Union($x,y$) là quan trọng, vì theo tứ tự đó, phần tử trái nhất còn trống của tập chứa $x$ nhỏ hơn của tập chứa $y$. Thứ nữa đó là trong hàm MakeSet($x$), phần tử ngay sau $X[x-1]$ có thể khác 0 (do đó trong comment mình để "supposed empty"). Nếu phần tử này khác 0, phép gộp trong hàm GreedyScheduling luôn đảm bảo tập hợp chứa $x-1$ sẽ được gộp với tập hợp chứa $x$.
Code: union-find-scheduling.
Tham khảo
[1] Avrim Blum. Note on Union-Find, CMU, 2011.
[2] Jeff Erickson. Note on Union-Find, UIUC, 2013.
[3] Jon Kleinberg and Eva Tardos. Algorithm Design, Chapter 4. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA,2005.
[4] Robert Endre Tarjan. Efficiency of a Good But Not Linear Set Union Algorithm. J. ACM 22, 2 (April 1975), 215-225. DOI=10.1145/321879.321884 http://doi.acm.org/10.1145/321879.321884
[5] Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford. Introduction to Algorithms (2nd ed.), Chapter 21 . MIT Press and McGraw-Hill (2001). ISBN 0-262-03293-7.
Recent Comments