Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
algo clips
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]])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment