algo clips

tournament_tree.py

import math


class WinnerTree:
    def __init__(self, ext):
        self.ext = ext
        self.N = len(ext)
        self.k = math.ceil(math.log(self.N, 2))
        print(self.k, ", bottom layer node ", pow(2, self.k))

    def get_v(self, tree_id):
        return self.ext[self.tree[tree_id]]

    def build_tree(self):
        # append bottom layer later
        self.tree = [-1] * (pow(2, self.k) - 1)
        self.bottom_start = len(self.tree)

        # tree node stores id of ext
        # so we append [0:N)
        self.tree += range(0, self.N)
        # print(self.tree)
        for i in range(self.bottom_start - 1, -1, -1):
            # print(i)
            left = 2 * i + 1
            right = 2 * i + 2
            if left < len(self.tree):
                self.tree[i] = self.tree[left]
            if right < len(self.tree):
                if self.get_v(right) < self.get_v(i):
                    self.tree[i] = self.tree[right]
        # print(tree)
        return self.tree

    def rebuild_tree(self, new_id):
        update_node = self.bottom_start + new_id
        while update_node > 0:
            parent = (update_node - 1) // 2
            bro = update_node + 1 if update_node % 2 == 1 else update_node - 1
            # update_node may be not the old winner
            self.tree[parent] = self.tree[update_node]
            if bro < len(self.tree) and self.get_v(update_node) >= self.get_v(bro):
                self.tree[parent] = self.tree[bro]
            update_node = parent
        return self.tree


ext = [5, 3, 2, 4, 7]
wt = WinnerTree(ext)
winner_tree = wt.build_tree()
print(winner_tree, ", min v is ", ext[winner_tree[0]])

# pop min, and push a new item
# winner tree can update any item in ext
ext[4] = -100

# rebuild winner tree, start from min_id(the node id is the )
winner_tree = wt.rebuild_tree(4)
print(winner_tree, ", min v is ", ext[winner_tree[0]])

ext = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
wt = WinnerTree(ext)
winner_tree = wt.build_tree()
print(winner_tree, ", min v is ", ext[winner_tree[0]])
ext[8] = -100
winner_tree = wt.rebuild_tree(8)
print(winner_tree, ", min v is ", ext[winner_tree[0]])


class LoserTree:
    def __init__(self, ext):
        self.ext = ext
        self.N = len(ext)
        self.k = math.ceil(math.log(self.N, 2))
        print(self.k, ", bottom layer node ", pow(2, self.k))

    def get_v(self, tree_id):
        return self.ext[self.tree[tree_id]]

    def build_tree(self):
        # winner use [0], [1:x] is the loser tree
        self.tree = [-1] * (pow(2, self.k))
        self.bottom_start = len(self.tree) - 1
        self.tree += range(0, self.N)
        # hard copy. leaf winner is itself, loser is whatever
        winners = list(self.tree)
        #         print(id(self.tree), id(winners))
        for i in range(self.bottom_start - 1, 0, -1):
            left = 2 * i
            right = 2 * i + 1
            if left < len(self.tree):
                winners[i] = winners[left]
                # loser is whatever
            if right < len(self.tree):
                if winners[right] < self.ext[winners[i]]:
                    # loser
                    self.tree[i] = winners[i]
                    # new winner
                    winners[i] = winners[right]
        #             print(self.tree)
        self.tree[0] = winners[1]
        return self.tree

    def rebuild_tree(self, new_id):
        print(self.ext)
        update_node = self.bottom_start + new_id
        temp_winner = new_id  # use ext[] to get value
        while update_node > 0:
            parent = update_node // 2
            loser = self.get_v(parent)
            if self.ext[temp_winner] >= loser:
                temp_winner = self.tree[parent]
                self.tree[parent] = temp_winner

            # temp_winner goes on
            update_node = parent
        if update_node == 0:
            self.tree[0] = temp_winner
        return self.tree

ext = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
wt = LoserTree(ext)
loser_tree = wt.build_tree()
print("winner of loser tree ", loser_tree, " is ", ext[loser_tree[0]])
# must update the winner in ext
ext[0] = -200
loser_tree = wt.rebuild_tree(0)
print("winner of loser tree ", loser_tree, " is ", ext[loser_tree[0]])