Advanced Data Structures

A binary heap is a complete binary tree stored in a flat array — children of index i live at 2i+1 and 2i+2, so no pointers are needed. The heap property (every parent ≤ its children, for a min-heap) is weaker than full ordering, which is exactly why push and pop are O(log n) rather than O(n log n): only one root-to-leaf path is repaired per operation.

import heapq

h = []
heapq.heappush(h, (2, "ship it"))
heapq.heappush(h, (1, "fix prod"))   # urgent
heapq.heappush(h, (3, "refactor"))

heapq.heappop(h)     # (1, "fix prod")
h[0]                 # peek — O(1)

# top-k without sorting everything: O(n log k)
heapq.nlargest(3, scores)

# max-heap: negate
heapq.heappush(h, (-priority, item))

Building a heap by n successive pushes costs O(n log n). Building it bottom-up (sift-down from index n//2−1 to 0) costs O(n): most nodes are near the leaves and sift down almost no levels, and the sum n/2·0 + n/4·1 + n/8·2 + … converges to n.

import heapq

a = [5, 3, 8, 1, 9, 2, 7, 4]
heapq.heapify(a)      # O(n) bottom-up, in place

# heapsort
def heapsort(a):
    heapq.heapify(a)                       # O(n)
    return [heapq.heappop(a) for _ in range(len(a))]

# why bottom-up is O(n):
# n/2 nodes sift 0 levels, n/4 sift 1, n/8 sift 2 ...
# sum(k * n / 2**(k+1)) -> n

A trie stores keys along the edges of a tree, so lookup is O(m) in the key length — independent of how many keys are stored. That is its real advantage over a hash map: not raw speed, but that prefix queries are free.

class Trie:
    def __init__(self):
        self.children = {}
        self.is_word = False

    def insert(self, word):
        node = self
        for ch in word:
            node = node.children.setdefault(ch, Trie())
        node.is_word = True          # matters!

    def find(self, prefix):
        node = self
        for ch in prefix:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node                  # subtree = all completions

# lookup is O(len(word)), NOT O(number of words)

DSU maintains a forest where each set is a tree with its root as the representative. Two optimisations make it fast: union by rank/size (always attach the smaller tree under the larger, keeping depth low) and path compression (on every find, re-point every node visited directly at the root).

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # compress
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                  # already together -> cycle
        if self.size[ra] < self.size[rb]:  # union by size
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        return True

A segment tree stores an associative aggregate (sum, min, max, gcd) for every node covering a contiguous range, in a 4n array. Both range query and point update are O(log n) because any range decomposes into at most O(log n) canonical nodes, and an update touches only the root path.

class SegTree:
    def __init__(self, a):
        self.n = len(a)
        self.t = [0] * (4 * self.n)
        self._build(a, 1, 0, self.n - 1)

    def _build(self, a, node, lo, hi):
        if lo == hi:
            self.t[node] = a[lo]; return
        mid = (lo + hi) // 2
        self._build(a, 2*node,   lo,      mid)
        self._build(a, 2*node+1, mid + 1, hi)
        self.t[node] = self.t[2*node] + self.t[2*node+1]

    def query(self, node, lo, hi, l, r):
        if r < lo or hi < l:  return 0            # disjoint
        if l <= lo and hi <= r: return self.t[node]  # fully inside
        mid = (lo + hi) // 2
        return (self.query(2*node,   lo,      mid, l, r) +
                self.query(2*node+1, mid + 1, hi,  l, r))

A Fenwick tree (binary indexed tree) stores, at index i, the sum of the i & -i elements ending at i. Prefix sum walks i -= i & -i; point update walks i += i & -i.

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.t = [0] * (n + 1)        # 1-indexed!

    def add(self, i, delta):
        while i <= self.n:
            self.t[i] += delta
            i += i & -i               # next block up

    def prefix(self, i):
        s = 0
        while i > 0:
            s += self.t[i]
            i -= i & -i               # strip lowest set bit
        return s

    def range_sum(self, l, r):
        return self.prefix(r) - self.prefix(l - 1)

A rotation is a constant-time, local restructuring that changes height while preserving the in-order sequence — the invariant that makes it legal. AVL trees keep every node's subtree heights within 1, giving tighter balance and faster lookups; red-black trees allow looser balance with fewer rotations per write, so they win on write-heavy workloads (which is why they back most standard libraries).

# Right rotation — O(1), and the in-order walk is unchanged
def rotate_right(y):
    x = y.left
    y.left = x.right
    x.right = y
    return x            # x is the new subtree root

def height(n):  return 0 if n is None else n.height
def balance(n): return height(n.left) - height(n.right)
# AVL invariant: abs(balance(n)) <= 1 for every node

# In practice, in Python:
from sortedcontainers import SortedDict
d = SortedDict()
d.irange(10, 20)      # ordered range query

Open addressing stores entries directly in the table and resolves collisions by probing: linear (i+1, cache-friendly but suffers primary clustering), quadratic (i+k², spreads clusters), or double hashing (step size from a second hash, best distribution). Deletion cannot simply clear a slot — that would truncate probe chains — so implementations write a tombstone, and tombstones accumulate until a rehash clears them.

# open addressing with linear probing + tombstones
EMPTY, TOMB = object(), object()

def find_slot(table, key):
    i = hash(key) % len(table)
    while table[i] is not EMPTY:
        if table[i] is not TOMB and table[i][0] == key:
            return i                    # found
        i = (i + 1) % len(table)        # probe on
    return None

# deleting must leave a TOMB, never EMPTY,
# or later probes stop early and lose entries

# load factor > ~0.7 -> resize and rehash everything

LRU needs O(1) lookup AND O(1) recency reordering, and no single structure gives both — so you compose two: a hash map for key → node, and a doubly linked list holding nodes in recency order. Lookup goes through the map; promotion unlinks the node and re-inserts at the head, which needs prev pointers, which is exactly why the list must be doubly linked.

from collections import OrderedDict

class LRU:
    def __init__(self, cap):
        self.cap, self.d = cap, OrderedDict()

    def get(self, k):
        if k not in self.d:
            return -1
        self.d.move_to_end(k)          # promote — O(1)
        return self.d[k]

    def put(self, k, v):
        if k in self.d:
            self.d.move_to_end(k)
        self.d[k] = v
        if len(self.d) > self.cap:
            self.d.popitem(last=False)  # evict oldest

# hash map = O(1) find, linked list = O(1) reorder
from functools import lru_cache        # the real one

A Bloom filter is a bit array plus k independent hash functions. Insert sets k bits; a query returns "possibly present" only if all k bits are set.

import hashlib

class Bloom:
    def __init__(self, m=1024, k=3):
        self.m, self.k = m, k
        self.bits = bytearray(m)

    def _hashes(self, item):
        h = hashlib.sha256(str(item).encode()).digest()
        return [int.from_bytes(h[i*4:(i+1)*4], "big") % self.m
                for i in range(self.k)]

    def add(self, item):
        for i in self._hashes(item):
            self.bits[i] = 1

    def __contains__(self, item):
        return all(self.bits[i] for i in self._hashes(item))
        # True  -> PROBABLY present
        # False -> DEFINITELY absent