Amortization & Union-Find

class DynamicArray:
    """
    Dynamic array with table doubling and halving.
    Amortized O(1) per append and delete (at end).
    Demonstrates the potential method concretely:
      Phi = 2*n - m  (where n = size, m = capacity)
      Phi >= 0 always (since n >= m/2 after any resize).
    """
    def __init__(self):
        self._data = [None]       # underlying storage, capacity m=1
        self._n    = 0            # number of elements

    def __len__(self): return self._n
    def __getitem__(self, i): return self._data[i]

    def append(self, val):
        """O(1) amortized. Actual cost: O(n) when doubling fires, O(1) otherwise."""
        if self._n == len(self._data):
            self._resize(2 * len(self._data))   # double: O(n), rare
        self._data[self._n] = val
        self._n += 1
        # Potential: Phi = 2*n - m
        # After append (no resize): delta_Phi = 2*(n+1)-m - (2*n-m) = 2
        # Amortized = 1 (actual) + 2 (delta_Phi) = 3 = O(1)
        # After append (with resize to 2m): delta_Phi = 2 - 2*m (big drop pays for resize)

    def pop(self):
        """O(1) amortized. Halve when table is 1/4 full to avoid thrashing."""
        if self._n == 0: raise IndexError
        val = self._data[self._n - 1]
        self._data[self._n - 1] = None
        self._n -= 1
        # Halve only at 1/4 full (not 1/2): avoids O(n) on alternating push/pop
        if self._n > 0 and self._n == len(self._data) // 4:
            self._resize(len(self._data) // 2)
        return val

    def _resize(self, new_cap):
        """Copy to new allocation. O(n)."""
        new_data = [None] * new_cap
        for i in range(self._n):
            new_data[i] = self._data[i]
        self._data = new_data

    def capacity(self): return len(self._data)


def demo_amortized_cost():
    """Measure actual vs amortized cost of n appends."""
    arr = DynamicArray()
    total_resizes = 0
    resize_costs  = 0
    n = 1024
    for i in range(n):
        old_cap = arr.capacity()
        arr.append(i)
        if arr.capacity() != old_cap:        # resize fired
            total_resizes += 1
            resize_costs  += old_cap          # O(old_cap) copy cost
    print(f"n={n}: {total_resizes} resizes, "
          f"total resize cost={resize_costs} ≈ {resize_costs/n:.1f}n")
    # Output: 10 resizes, total resize cost≈2n (confirming O(1) amortized)

class UnionFind:
    """
    Disjoint Set Union (DSU) with:
      - Union by rank: attach smaller-rank tree under larger-rank root
      - Path compression: flatten tree on every FIND-SET
    Amortized O(alpha(n)) per operation — essentially O(1) in practice.
    """
    def __init__(self, n):
        self.parent = list(range(n))   # parent[x] = x means x is a root
        self.rank   = [0] * n          # upper bound on height of subtree
        self.n_components = n

    def find(self, x):
        """
        Find representative of x. Path compression: redirect all nodes
        on the path directly to the root (two-pass or iterative).
        """
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        """
        Merge sets containing x and y. Union by rank: attach smaller
        rank tree under larger rank root. Return True if merged, False if same set.
        """
        rx, ry = self.find(x), self.find(y)
        if rx == ry: return False          # already in same set

        # Union by rank: smaller rank attaches under larger rank
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx                # ensure rank[rx] >= rank[ry]
        self.parent[ry] = rx               # attach ry under rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1             # only increase rank on tie
        self.n_components -= 1
        return True

    def connected(self, x, y):
        """O(alpha(n)) amortized."""
        return self.find(x) == self.find(y)

    def component_count(self):
        return self.n_components


def kruskal_mst(n, edges):
    """
    Kruskal's MST using Union-Find.
    edges: list of (weight, u, v). Returns MST edges.
    O(E log E) — dominated by sorting; Union-Find is O(E * alpha(V)).
    """
    edges.sort()                           # sort by weight
    uf  = UnionFind(n)
    mst = []
    for w, u, v in edges:
        if uf.union(u, v):                 # adds edge only if u,v not connected
            mst.append((w, u, v))
        if len(mst) == n - 1:
            break                          # MST complete
    return mst

class BinaryCounter:
    """
    Binary counter demonstrating potential method for amortized analysis.
    Phi = number of 1-bits.
    Amortized cost per increment = O(1), even though actual cost can be O(k).
    """
    def __init__(self, bits=16):
        self.bits  = [0] * bits
        self.total_actual_cost = 0

    def increment(self):
        """Flip trailing 1s to 0, then flip first 0 to 1."""
        i, flips = 0, 0
        while i < len(self.bits) and self.bits[i] == 1:
            self.bits[i] = 0
            i += 1
            flips += 1
        if i < len(self.bits):
            self.bits[i] = 1
            flips += 1
        self.total_actual_cost += flips
        return flips

    def phi(self):
        """Potential = number of 1-bits."""
        return sum(self.bits)

    def verify_amortized(self, n_increments):
        """
        Verify: total actual cost <= 2 * n_increments (O(1) amortized).
        Amortized cost per increment = actual + delta_Phi = flips + (1 - flips) = 1 + ... = 2.
        """
        counter = BinaryCounter()
        for i in range(n_increments):
            counter.increment()
        ratio = counter.total_actual_cost / n_increments
        print(f"n={n_increments}: total_cost={counter.total_actual_cost}, "
              f"ratio={ratio:.3f} (should be < 2)")

# Verify for several n
for n in [100, 1000, 10000, 100000]:
    BinaryCounter().verify_amortized(n)


def potential_method_demo():
    """
    Demonstrate potential method for table doubling.
    Phi = 2*n - capacity. Show that amortized cost per append = O(1).
    """
    arr  = DynamicArray()
    phi  = lambda: 2 * len(arr) - arr.capacity()
    prev_phi = phi()
    total_amortized = 0

    for i in range(32):
        prev_phi = phi()
        arr.append(i)
        new_phi  = phi()
        actual   = 1 if arr.capacity() == (arr.capacity()) else arr.capacity() // 2 + 1
        delta    = new_phi - prev_phi
        amortized = 1 + delta        # always approximately 3 or less
        total_amortized += abs(amortized)

    print(f"Total amortized (32 appends) = {total_amortized}")  # ≈ 96 = 3*32