Data Structure
Heap - O(log n) Remove
class MinHeap:
def __init__(self):
self.q = []
self.nums = dict()
self.size = 0
def __len__(self):
return self.size
def add(self, num):
if num in self.nums:
self.nums[num] += 1
else:
heapq.heappush(self.q, num)
self.nums[num] = 1
self.size += 1
def remove(self, num):
if num not in self.nums:
return
self.nums[num] -= 1
if self.nums[num] == 0:
del self.nums[num]
while self.q and self.q[0] not in self.nums:
heapq.heappop(self.q)
self.size -= 1
def top(self):
return self.q[0]
def pop(self):
num = self.top()
self.remove(num)
return num
class PriorityQueue:
def __init__(self):
self.q = []
self.entries = dict()
def __len__(self):
return len(self.entries)
def add(self, task, priority=0):
if task in self.entries:
self.remove(task)
entry = [priority, task]
heapq.heappush(self.q, entry)
self.entries[task] = entry
def remove(self, task):
if task not in self.entries:
return
self.entries.pop(task)[1] = None
while self.q and self.q[0][1] is None:
heapq.heappop(self.q)
def top(self):
return self.q[0][1]
def pop(self):
task = self.top()
self.remove(task)
return task
class Trie:
def __init__(self):
self.root = dict()
def add(self, word):
node = self.root
for char in word:
if char not in node:
node[char] = dict()
node = node[char]
node['#'] = word
def search(self, word, prefix=False):
node = self.root
for char in word:
if char not in node:
return False
node = node[char]
return True if prefix else '#' in node
Union-find - Path Compression & Weighted Merge
class UnionFind:
def __init__(self, n):
self.parent = [-1] * n
self.size = [0] * n
self.count = 0
def __len__(self):
return self.count
def add(self, num):
if 0 <= num < len(self.parent):
self.parent[num] = num
self.size[num] = 1
self.count += 1
def find(self, num):
if 0 <= num < len(self.parent):
root = num
while root >= 0 and root != self.parent[root]:
root = self.parent[root]
self.parent[num] = root
return root
return -1
def union(self, num1, num2):
u = self.find(num1)
v = self.find(num2)
if u < 0 or v < 0 or u == v:
return
big, small = (u, v) if self.size[u] > self.size[v] else (v, u)
self.parent[small] = big
self.size[big] += self.size[small]
self.count -= 1
class UnionFind:
def __init__(self, n):
self.unions = [[]] * n
self.count = 0
def __len__(self):
return self.count
def add(self, num):
if 0 <= num < len(self.unions):
self.unions[num] = [num]
self.count += 1
def find(self, num):
if 0 <= num < len(self.unions):
return self.unions[num]
return []
def union(self, num1, num2):
u = self.find(num1)
v = self.find(num2)
if not u or not v or u is v:
return
big, small = (u, v) if len(u) > len(v) else (v, u)
for num in small:
self.unions[num] = big
big.extend(small)
self.count -= 1