Personal Learning record:one of Abstract Date Type(ADT)---Disjoint Set(by python)

0. record all brunch of boxes and lines X complicated(graph)

I.A Better Approach: Connected Compnents 1 track the sets which membership in

just need to record which set each item belongs to
in other words, when we first start, each item is in its own set
(and then when we connnect 1 and 2, we put them in the same set or merge these sets)

2.What data structure can be use to track the set? a list of set of integers?

x complicated and sloooow

a list of integers?

√like this

In id list, the ith entry tells us the set number of i.

it named QuickFind

class QuickFindDS(object):
	def __init__(self, N):
		self.__id = list(range(0,N))
		print(self.__id)

	def isConnected(self, p, q):#very fast
		return self.__id[p] == self.__id[q]
		
	def connect(self, p, q):#slow
		"""We want to change every id equal to p's id to be equal q's id"""
		pid = self.__id[p]
		qid = self.__id[q]
		# if x == pid: this item = qid, otherwise we just keep x 
		self.__id = [qid if x == pid else x for x in self,__id]

ds = QuickFindDS(7)
# ds.connect(0,1)
print(ds.isConnected(1,2))

But, the Big-Theta of its Connect is N, it is relatively slow.

II.Improving the Connect Operation 1.QuickUnion

we can give them parent~
using parent to only chage one value when we try to combine two sets.(before we needed to change potentially several values)
So when connecting, we just need connect the root of the two values.

how to connect?

1. find the item’s root (5)
2. find another item’s root (2)
3. set the root of 5’s value to root 2;

like this

Considering the worst case:
new question appear: if the tree is very tall potentially this(connect and IsConnect) could be slow(Big O = N)

(we can keep the tree balance, reduce its height)

2. WeightedQuickUnion

In order to reduce the runtime of connect/IsConnect , we can balance the tree(min the height of the tree)
SO,we are always going to link the root of smaller tree(the number of elements) to the larger tree.

(but this operation using the weight instead of height, why?)

The worst situation of this is: always connect two equal-weight trees, the heigt is log(a tree which is logarithmic in height), pretty good

For why did we pick weight instead of height? The worst case performance for heighted QuickUniono is going t be the same. The worst case runtime is also Theta(logN). In other words, heighted QuickUnion has the exact same asymptotic performance as weightedQuickUnion. Chosing weight is a simpler solution.
two lists parents, size

Path Compression

With path compression, what we do is to tie every item that we saw along that path to the root.

The Big O decline dramatically.

class WeightQuinkUnionWithPathCompression(object):
	"""docstring for WeightQuinkUnion"""
	def __init__(self, N):
		self.__id = list[range(0,N)]
		self.__size = [1 for _ in range(N)]
		
	def getroot(self, p):
		if self.__size[p] == p:
			return p
		pid = getroot(self.__id[p])
		self.__id[p] = pid
		return pid

	def IsConnect(self, a, b):
		return self.getroot(a) == self.getroo(b)

	def connect(self, a, b):
		rta = self.getroot(a)
		rtb = self.getroot(b)
		if self.__size[rta] > self.__size[rtb]:
			self.__id[rtb] = self.__id[rta]
			self.__size[rta] += self.__size[rtb]
		else:
			self.__id[rta] = self.__id[rtb]
			self.__size[rtb] += self.__size[rta]
	#Written my myself, there may be some errors here. welcome correct and criticism

暑期编程PK赛 得CSDN机械键盘等精美礼品！