Advanced Data Structures
Open in the Padhaiko app2.1 Fibonacci heaps
A Fibonacci heap is a collection of min-heap-ordered rooted trees that supports mergeable-heap operations with better amortized bounds than binary or binomial heaps, making it the classic priority queue behind Dijkstra's algorithm and Prim's algorithm.
Structure and Potential of a Fibonacci Heap
A Fibonacci heap consists of a circular, doubly linked root list of min-heap-ordered trees, a pointer H.min to the root with minimum key, and the node count H.n. Each node stores:
x.key,x.parent,x.child(pointer to one child in a circular doubly linked child list),x.degree: number of children of ,x.mark: boolean flag recording whether has lost a child since the last time became a child of another node (alwaysFalsefor roots).
Using for the number of trees in the root list and for the number of marked nodes, the potential function is:
Operations and Amortized Bounds
INSERT(H, x)— amortized: Creates a singleton tree containing (x.mark = False), splices it into the root list, and updatesH.min. Actual cost is and , so amortized cost is .UNION(H1, H2)— amortized: Concatenates the two circular root lists in time and picks the smallerminpointer ().EXTRACT-MIN(H)— amortized:- Promotes every child of
H.mininto the root list (clearing theirmarkbits) and removesH.min. - Consolidates the root list so that no two roots have the same degree: using an array
A[0..D(n)], whenever two roots share degree , the larger-key root is linked as a child of the smaller-key root, increasing its degree to . - Because consolidation takes actual time and reduces to at most , the potential drop pays for processing the old roots, leaving amortized cost .
- Promotes every child of
DECREASE-KEY(H, x, k)— amortized:- Updates
x.key = k. If the heap property withy = x.parentis violated, cut from , move to the root list, and clearx.mark. - Cascading cut on : if
yis not a root andy.mark == False, sety.mark = Trueand stop. Ify.mark == True, cutyfrom its parent, moveyto the root list (y.mark = False), and continue upward until reaching an unmarked node or a root. - If cascading cuts occur, actual cost is , , and , giving:
- Updates
so the terms cancel and the amortized cost is .
DELETE(H, x)— amortized: PerformsDECREASE-KEY(H, x, -\infty)() followed byEXTRACT-MIN(H)().
Maximum Degree Bound via Fibonacci Numbers
Every node of degree in an -node Fibonacci heap has subtree size at least , where is the -th Fibonacci number () and . Consequently, the maximum degree of any node satisfies:
| Operation | Binary Heap (Worst-Case) | Binomial Heap (Worst-Case) | Fibonacci Heap (Amortized) |
|---|---|---|---|
MAKE-HEAP | |||
INSERT | |||
MINIMUM | |||
EXTRACT-MIN | |||
UNION | |||
DECREASE-KEY | |||
DELETE |
2.2 Splay trees
A splay tree (Sleator & Tarjan, 1985) is a self-adjusting binary search tree that maintains no balance metadata (no height, color, or size fields) yet guarantees amortized time per dictionary operation (SEARCH, INSERT, DELETE, SPLIT, JOIN).
Splaying Rotations (Zig, Zig-Zig, Zig-Zag)
Whenever a node is accessed, SPLAY(x) repeatedly rotates upward until becomes the root of the tree, choosing one of three cases at each step based on 's parent and grandparent :
- Zig (single rotation): is the root. Rotate edge (left if is right child of , right if is left child).
- Zig-Zig (same-side double rotation): is not the root, and and are both left children (or both right children). First rotate , then rotate .
- Zig-Zag (opposite-side double rotation): is not the root, and is a left child while is a right child (or vice versa). First rotate , then rotate .
Amortized Analysis (Access Lemma)
Assign each node a positive weight (commonly ). Let be the subtree weight and define the rank , with potential .
Splay Access Lemma and Optimality Properties
For a single splay step on moving to with root :
- Zig: amortized cost .
- Zig-Zig and Zig-Zag: amortized cost .
Telescoping over the entire SPLAY(x) to root gives amortized cost at most . Setting weights appropriately yields:
- Static Optimality: Total access time for queries is within a constant factor of the best static binary search tree.
- Working-Set Property: Accessing an item accessed distinct items ago costs amortized time (strong temporal locality).
1
- In a Fibonacci heap, find the minimum possible number of nodes in a tree rooted at a node of degree . What is the maximum possible node degree in a Fibonacci heap containing nodes?
- A left-leaning chain of nodes has root , left child , left grandchild , and left great-grandchild . Trace
SPLAY(10)step by step, naming each rotation case.
Fibonacci heap minimum subtree size for degree : By Theorem 2.1, a node of degree has at least nodes in its subtree (counting itself). For , we need :
So a degree- node requires at least nodes.
Maximum degree for nodes: Find the largest such that :
Since gives , the maximum possible degree is . (Equivalently, .)
Trace SPLAY(10) on the left chain :
- First step (Zig-Zig at ): Both and are left children. First right-rotate so becomes the left child of with right child . Next right-rotate so becomes the left child of , with right child (whose right child is ).
- Second step (Zig at ): Now is the root and is its left child. Right-rotate . Now is the root, its right child is , 's left child is , and 's right child is (depth reduced from to ).
- Minimum subtree size for degree is nodes (); maximum degree in a -node Fibonacci heap is .
SPLAY(10)performs a left-left Zig-Zig on followed by a left Zig on , leaving at the root with right spine .
2.3 Bloom filters
A Bloom filter (Burton Bloom, 1970) is a compact, probabilistic bit-array data structure for testing set membership (INSERT and QUERY) in time using far less memory than storing the keys themselves.
Bloom Filter Parameters and Operations
A Bloom filter consists of:
- An array of bits, all initialized to .
- independent, uniform hash functions .
Operations:
INSERT(x): Compute and set for all .QUERY(x): ReturnTrue("possibly in set") if for all ; returnFalse("definitely not in set") if any .
- Zero False Negatives: If was inserted, all bits were set to and are never cleared, so
QUERY(x)always returnsTrue. - No Standard Deletion: Clearing a bit could corrupt membership of another element that hashes to the same bit (a Counting Bloom Filter replaces each bit with a small counter to support deletion).
False Positive Probability and Optimal Sizing
After inserting distinct elements ( independent bit-setting probes), the probability that a specific bit remains is:
For an uninserted query element , all probed bits are (a false positive) with probability:
Minimizing with respect to yields the optimal number of hash functions and required bit-array size:
2
A Bloom filter has bits and is designed to store keys.
- Calculate the optimal number of hash functions (rounded to the nearest integer).
- Using that integer , compute the resulting false positive probability .
Optimal number of hash functions:
False positive probability for :
The optimal integer number of hash functions is , yielding a false positive probability of () using only bits ( bytes) per key.
2.4 Segment trees
A segment tree is a static binary tree built over an array that supports both associative range queries (such as range sum, range minimum/maximum, range GCD, or XOR) and updates in time.
Segment Tree Node Invariant and Layout
Each node in a segment tree corresponds to a contiguous subarray interval :
- If (a leaf), stores .
- If (an internal node) with midpoint , the left child covers , the right child covers , and stores the associative aggregate .
Using 1-based heap indexing (left = 2*v, right = 2*v + 1), an array of size guarantees no out-of-bounds access for any .
Complexities and Lazy Propagation
BUILD: Recursively computes leaves and merges upward in time.POINT-UPDATE(idx, val): Walks down the single root-to-leaf path containingidxand recomputes ancestors on return in time.RANGE-QUERY(ql, qr): Visits at most nodes per level of the tree (since at most two partial overlaps occur on the left and right boundaries of ), running in time.- Lazy Propagation (
RANGE-UPDATE): To add to every element in in time, each node stores alazy[v]tag of pending updates. When completely covers node 's interval , updatetree[v]immediately, accumulate intolazy[v], and stop recursing. Whenever a future query or update must descend into 's children, first push downlazy[v]to2*vand2*v+1and resetlazy[v] = 0.
class SegmentTree:
def __init__(self, arr):
self.n = len(arr)
self.tree = [0] * (4 * self.n)
if self.n > 0:
self._build(arr, 1, 0, self.n - 1)
def _build(self, arr, v, l, r):
if l == r:
self.tree[v] = arr[l]
return
m = (l + r) // 2
self._build(arr, 2 * v, l, m)
self._build(arr, 2 * v + 1, m + 1, r)
self.tree[v] = self.tree[2 * v] + self.tree[2 * v + 1]
def update(self, idx, val, v=1, l=0, r=None):
if r is None:
r = self.n - 1
if l == r:
self.tree[v] = val
return
m = (l + r) // 2
if idx <= m:
self.update(idx, val, 2 * v, l, m)
else:
self.update(idx, val, 2 * v + 1, m + 1, r)
self.tree[v] = self.tree[2 * v] + self.tree[2 * v + 1]
def query(self, ql, qr, v=1, l=0, r=None):
if r is None:
r = self.n - 1
if ql > r or qr < l:
return 0
if ql <= l and r <= qr:
return self.tree[v]
m = (l + r) // 2
return self.query(ql, qr, 2 * v, l, m) + self.query(ql, qr, 2 * v + 1, m + 1, r)2.5 Disjoint set union
A Disjoint Set Union (DSU) or Union-Find structure maintains a collection of pairwise disjoint dynamic sets over elements, identifying each set by a canonical representative.
Disjoint Set Operations
MAKE-SET(x): Creates a new singleton set with representative .FIND-SET(x): Returns a pointer to the representative of the unique set currently containing .UNION(x, y): Replaces the two sets and containing and with their union (if ).
Representing each set as a rooted tree where parent[x] points toward the root (and parent[root] = root), naive UNION can create a degenerate chain of height , making FIND-SET take time. Two classic heuristics eliminate this:
- Union by Rank (or Union by Size): Maintain
rank[root](an upper bound on subtree height). When merging two roots and , attach the smaller-rank root under the larger-rank root; incrementrankby only whenrank[r_x] == rank[r_y]. Alone, this guarantees tree height , giving worst-case time per operation. - Path Compression: During
FIND-SET(x), after finding the root , redirectparent[u] = rfor every node visited along the find path so subsequent lookups reach in time.
Tarjan's Amortized Bound for DSU
With both union by rank (or size) and path compression, any sequence of MAKE-SET, UNION, and FIND-SET operations on elements runs in:
total time, where is the inverse Ackermann function ( for every up to , making each operation effectively constant time in practice).
3
- Build a range-sum segment tree over the array (0-indexed). List the values at the root and its children and , compute
query(1, 4), and find the updated values afterupdate(2, 7). - Starting from singleton sets (all rank ), trace
UNION(1, 2),UNION(3, 4),UNION(2, 4)(attach second root under first on tie),UNION(5, 6),UNION(4, 6), andFIND-SET(6)with path compression.
Segment tree node values and query on :
- Left half sums (split into and ).
- Right half sums (split into and ).
- Root stores .
- Query decomposes into (), (), and (), returning .
- After
update(2, 7)(increase by ), nodes , , and ; nowquery(1, 4)returns .
DSU trace with union by rank and path compression:
UNION(1, 2): ranks equal ()parent[2] = 1,rank[1] = 1.UNION(3, 4): ranks equal ()parent[4] = 3,rank[3] = 1.UNION(2, 4):FIND(2) = 1(rank ),FIND(4) = 3(rank ). Tieparent[3] = 1,rank[1] = 2.UNION(5, 6): ranks equal ()parent[6] = 5,rank[5] = 1.UNION(4, 6):FIND(4)walks (compressesparent[4] = 1);FIND(6) = 5(rank ). Sincerank[1] = 2 > rank[5] = 1,parent[5] = 1(rank[1]stays ).FIND-SET(6): walks , returning representative and compressingparent[6] = 1directly.
- Initial segment tree: root , left , right ,
query(1, 4) = 19. Afterupdate(2, 7): root , , andquery(1, 4) = 25. - After all unions and
FIND-SET(6), the single tree has root (rank = 2) with direct children .
Exercises
Practice Exercises — Advanced Data Structures
Define the potential function of a Fibonacci heap and prove why DECREASE-KEY achieves amortized time even when cascading cuts occur. Suppose a heap has root trees and marked nodes, and DECREASE-KEY performs an initial cut plus cascading cuts (causing the final unmarked ancestor, which is not a root, to become marked). Compute , , and .
Amortized proof for DECREASE-KEY with cascading cuts: Suppose DECREASE-KEY(H, x, k) performs initial cut of and cascading cuts of marked ancestors before stopping at an unmarked ancestor (or a root). Each cut takes actual work, so total actual cost is (in unit-cost steps).
- Each of the cuts adds a new tree to the root list, so .
- Each of the cascadingly cut ancestors was previously marked and becomes unmarked when promoted to a root, while at most unmarked ancestor becomes newly marked, so .
- Therefore , and amortized cost .
Numerical potential change ():
- Initial potential: .
- After cuts: .
- Two marked nodes lose their marks () and the final non-root ancestor becomes marked (): .
- New potential: , so .
gives , canceling the cascading-cut cost to leave amortized time. In the given state, , , and .
Explain the three rotation cases (Zig, Zig-Zig, and Zig-Zag) in a splay tree and state why Zig-Zig rotates before rather than rotating up one edge at a time. Starting from a right-leaning chain (root ), trace SPLAY(5) and show the resulting tree shape.
Three rotation cases and why Zig-Zig order matters:
- Zig: is the root; perform one single rotation on .
- Zig-Zig: and are on the same side of their parents; rotate first, then .
- Zig-Zag: and are on opposite sides; rotate first, then .
Rotating first in Zig-Zig compresses paths by halving the depth of nodes along the path; naive bottom-up single rotations merely shift the chain to the other side without shrinking depth, failing the amortized bound.
Trace SPLAY(5) on right chain :
- Zig-Zig on : Left-rotate giving (with left child , right child ), then left-rotate giving (with left child , whose left child is ).
- Zig-Zig on : Left-rotate giving root (left child , right child ), then left-rotate giving root with left child , 's left child , and 's right child (whose left child is ).
Zig handles a root parent, Zig-Zig handles same-side grandparent paths ( then to halve depths), and Zig-Zag handles opposite-side paths. After SPLAY(5) on , is the root with left child , where has left child and right child (with left child ), reducing max depth from to .
A web crawler needs a Bloom filter to track visited URLs with a target false positive rate of (). Compute the required bit-array size (in bits and KB) and the optimal number of hash functions . Also explain why standard Bloom filters do not support deletion and how Counting Bloom Filters solve this.
Compute bit-array size :
Compute optimal and explain deletion:
Standard Bloom filters cannot delete a key by resetting its bits to because another inserted key may share one or more of those bit positions, causing false negatives. A Counting Bloom Filter replaces each -bit cell with a small multi-bit counter (typically bits), incrementing on insert and decrementing on delete.
The Bloom filter needs bits () and hash functions. Standard Bloom filters prohibit deletion because clearing shared bits creates false negatives; Counting Bloom Filters solve this by storing small integer counters instead of single bits.
Explain how lazy propagation enables range updates in a segment tree. Given the -element array (0-indexed), suppose we execute a range-add update adding to all indices in followed by a range-sum query on . Trace which nodes receive lazy tags and compute the resulting sum.
Lazy propagation mechanism: When a range update covers a segment tree node's interval completely, we update tree[v] += (r - l + 1) * delta, store lazy[v] += delta, and return immediately without descending to descendants. Pending tags are pushed down to children only when a subsequent traversal needs to inspect a strict subinterval of , keeping both range updates and range queries at .
Trace range-add on over : The root splits into and :
- In : is outside ; is completely inside , so
tree[[2,3]]increases from to and receiveslazy = +3. - In : is completely inside , so
tree[[4,5]]increases from to and receiveslazy = +3. On , is outside and leaf increases from to . - Querying visits the exact same three covering nodes , , and :
Lazy propagation defers updates to descendants in lazy[v] until a child is visited. Adding on sets lazy tags on and (plus leaf ), yielding a range sum of .
State the worst-case time complexity of Disjoint Set Union (DSU) with (a) naive linking, (b) union by rank only, and (c) union by rank combined with path compression for a sequence of operations on elements. Prove why union by rank alone bounds the height of any tree in the forest to at most .
Complexities for operations on elements:
- (a) Naive linking: (degenerate chain of length ).
- (b) Union by rank only: (each
FIND-SETtraverses at most the tree height ). - (c) Union by rank + path compression: amortized, where is the inverse Ackermann function.
Proof by induction that a root of rank has at least nodes:
- Base case (): A singleton tree has node.
- Inductive step: A tree's rank increases from to only when two trees of equal rank are merged. By the inductive hypothesis, each tree has at least nodes, so the merged tree has at least nodes. (Merging unequal ranks leaves the larger rank unchanged and strictly increases node count.)
Since the total number of nodes is , we have . Without path compression, rank equals tree height, so height .
DSU takes naively, with union by rank alone, and amortized with union by rank plus path compression. By induction, any rank- tree contains at least nodes, bounding height by .