Non Built-in Data Structures And Algorithms in Python3

Unordered MultiSet

class MultiSet:
    def __init__(self):
        self.data = dict()
    
    def add(self, val):
        self.data[val] = 1 + (self.data[val] if val in self.data else 0)
    
    def remove(self, val):
        if not val in self.data:
            return
        self.data[val] -= 1
        if self.data[val] == 0:
            del self.data[val]

Fenwick Tree / Binary-indexed Tree

class BIT:
    def __init__(self, size):
        self.size = size
        self.data = [0] * size
    
    def add(self, pos, val):
        while pos < self.size:
            self.data[pos] += val
            pos += pos & (-pos)
    
    def query(self, pos):
        res = 0
        while pos > 0:
            res += self.data[pos]
            pos &= pos - 1
        return res

Binary Heap / Priority Queue

Sample

Skip List

Sample 1
Sample 2

Red Black Tree

Sample 1
Sample 2

Next Permutation