algs class

quick_find.py

# union - N operations
# find = 1 operation

class QuickFind(object):

    def __init__(self, N):
        self.entry_list = range(0, N)

    def connected(self, p, q):
        return self.entry_list[p] == self.entry_list[q]

    def union(self, p, q):
        for index, entry in enumerate(self.entry_list):
            if entry == self.entry_list[p] or entry == p:
                self.entry_list[index] = self.entry_list[q]
        print "{}-{}:  {}".format(str(p), str(q), " ".join(map(str, self.entry_list)))

quick_union.py

# union - N operations
# find - N operations

class QuickUnion(object):

    def __init__(self, N):
        self.entry_list = range(0, N)

    def connected(self, p, q):
        return self.get_root(p) == self.get_root(q)

    def get_root(self, i):
        while(self.entry_list[i] != i):
            i = self.entry_list[i]

        return i

    def union(self, p, q):
        i = self.get_root(p)
        j = self.get_root(q)
        self.entry_list[i] = j

weighted_quick_union.py

# union: lg N
# connected: lg N

class WeightedQuickUnion(object):

    def __init__(self, N):
        self.entry_list = range(0, N)
        self.tree_sizes = [1 for i in self.entry_list]

    def connected(self, p, q):
        return self.get_root(p) == self.get_root(q)

    def get_root(self, i):
        while(self.entry_list[i] != i):
            i = self.entry_list[i]

        return i

    def union(self, p, q):
        i = self.get_root(p)
        j = self.get_root(q)

        if i == j:
            return

        if self.tree_sizes[i] < self.tree_sizes[j]:
            self.entry_list[i] = j
            self.tree_sizes[j] += self.tree_sizes[i]
        else:
            self.entry_list[j] = i
            self.tree_sizes[i] += self.tree_sizes[j]

        print "{}-{}:  {}".format(str(p), str(q), " ".join(map(str, self.entry_list)))

weighted_quick_union_with_path_compresssion.py

class WeightedQuickUnionWithPathCompression(object):

    def __init__(self, N):
        self.entry_list = range(0, N)
        self.tree_sizes = [1 for i in self.entry_list]

    def connected(self, p, q):
        return self.get_root(p) == self.get_root(q)

    def get_root(self, i):
        while(self.entry_list[i] != i):
            # dongu icinde top parent'a kadar yol alinirken
            # yoldaki elemanlar da parent'a esitleniyor.
            # bu elemanlar bir daha istendigi zaman
            # tree'deki path sayisi azaliyor.
            
            self.entry_list[i] = self.entry_list[self.entry_list[i]]
            i = self.entry_list[i]

        return i

    def union(self, p, q):
        i = self.get_root(p)
        j = self.get_root(q)

        if i == j:
            return

        if self.tree_sizes[i] < self.tree_sizes[j]:
            self.entry_list[i] = j
            self.tree_sizes[j] += self.tree_sizes[i]
        else:
            self.entry_list[j] = i
            self.tree_sizes[i] += self.tree_sizes[j]