Binomial Queue Visualization

A collection of binomial trees with unique ranks, supporting efficient merge operations. Operations work like binary addition!

Binary-Addition Style Merging

🌲 Forest of Binomial Trees

Binomial Queue Visualization

Speed:

🌲

Empty Binomial Queue

Trees

Total Nodes

Ranks

Current Step:

Select an operation to begin visualization

Complexity Analysis

O(log n)

Insert*

O(log n)

Extract Min

O(log n)

Find Min

O(log n) Merge

Efficient queue union

*O(1) amortized for insert

Binomial Tree B_k

• Definition: B₀ is a single node, and B_k = B_(k-1) + B_(k-1)

• Node Count: Exactly 2^k nodes in B_k

• Height: Height of B_k is k

• Children: Root has k children: B_(k-1), B_(k-2), ..., B_0

• Merge Rule: Two B_k trees merge to form B_(k+1)

• Min-Heap: Every parent ≤ children

Binary Addition Analogy

• Each rank represents a bit position

• At most one tree per rank (like 0 or 1)

• Two trees of rank k → one tree of rank k+1 (carry)

• Insert is like adding 1 in binary

• Example: 13 nodes = 1101₂ → trees of rank 0, 2, 3

5 nodes = 101₂ → B₀ + B₂
+1 → 110₂ → B₁ + B₂

Applications

• Union-Find: Efficient merging of priority queues

• External Sorting: K-way merge with large datasets

• Parallel Algorithms: Distributed priority queues

• Event Simulation: When merging queues is common

Implementation

class BinomialTreeNode:
    def __init__(self, value):
        self.value = value
        self.rank = 0
        self.children = []
        self.parent = None

class BinomialQueue:
    def __init__(self):
        self.trees = []  # List of binomial trees sorted by rank
    
    def merge_trees(self, t1, t2):
        """Merge two binomial trees of same rank"""
        if t1.value <= t2.value:
            t1.children.append(t2)
            t2.parent = t1
            t1.rank += 1
            return t1
        else:
            t2.children.append(t1)
            t1.parent = t2
            t2.rank += 1
            return t2
    
    def insert(self, value):
        """Insert a new value - O(log n) amortized"""
        new_tree = BinomialTreeNode(value)
        self._merge_queue([new_tree])
    
    def _merge_queue(self, other_trees):
        """Merge another binomial queue (like binary addition)"""
        all_trees = sorted(self.trees + other_trees, 
                          key=lambda t: t.rank)
        
        result = []
        carry = None
        i = 0
        
        while i < len(all_trees) or carry:
            # Collect trees of same rank
            candidates = []
            if carry:
                candidates.append(carry)
            
            while i < len(all_trees):
                if not candidates or \
                   all_trees[i].rank == candidates[0].rank:
                    candidates.append(all_trees[i])
                    i += 1
                    if len(candidates) >= 2:
                        break
                else:
                    break
            
            # Handle different cases
            if len(candidates) == 1:
                result.append(candidates[0])
                carry = None
            elif len(candidates) == 2:
                carry = self.merge_trees(candidates[0], candidates[1])
            elif len(candidates) == 3:
                result.append(candidates[2])
                carry = self.merge_trees(candidates[0], candidates[1])
        
        self.trees = result
    
    def find_min(self):
        """Find minimum value - O(log n)"""
        if not self.trees:
            return None
        return min(tree.value for tree in self.trees)
    
    def extract_min(self):
        """Remove and return minimum - O(log n)"""
        if not self.trees:
            return None
        
        # Find tree with minimum root
        min_tree = min(self.trees, key=lambda t: t.value)
        min_value = min_tree.value
        
        # Remove min tree from queue
        self.trees.remove(min_tree)
        
        # Children become new binomial queue
        children_queue = list(reversed(min_tree.children))
        
        # Merge the two queues
        self._merge_queue(children_queue)
        
        return min_value
    
    def size(self):
        """Return number of elements - O(log n)"""
        count = 0
        for tree in self.trees:
            count += 2 ** tree.rank
        return count

Implementation

class BinomialTreeNode: def __init__(self, value): self.value = value self.rank = 0 self.children = [] self.parent = None class BinomialQueue: def __init__(self): self.trees = [] # List of binomial trees sorted by rank def merge_trees(self, t1, t2): """Merge two binomial trees of same rank""" if t1.value <= t2.value: t1.children.append(t2) t2.parent = t1 t1.rank += 1 return t1 else: t2.children.append(t1) t1.parent = t2 t2.rank += 1 return t2 def insert(self, value): """Insert a new value - O(log n) amortized""" new_tree = BinomialTreeNode(value) self._merge_queue([new_tree]) def _merge_queue(self, other_trees): """Merge another binomial queue (like binary addition)""" all_trees = sorted(self.trees + other_trees, key=lambda t: t.rank) result = [] carry = None i = 0 while i < len(all_trees) or carry: # Collect trees of same rank candidates = [] if carry: candidates.append(carry) while i < len(all_trees): if not candidates or \ all_trees[i].rank == candidates[0].rank: candidates.append(all_trees[i]) i += 1 if len(candidates) >= 2: break else: break # Handle different cases if len(candidates) == 1: result.append(candidates[0]) carry = None elif len(candidates) == 2: carry = self.merge_trees(candidates[0], candidates[1]) elif len(candidates) == 3: result.append(candidates[2]) carry = self.merge_trees(candidates[0], candidates[1]) self.trees = result def find_min(self): """Find minimum value - O(log n)""" if not self.trees: return None return min(tree.value for tree in self.trees) def extract_min(self): """Remove and return minimum - O(log n)""" if not self.trees: return None # Find tree with minimum root min_tree = min(self.trees, key=lambda t: t.value) min_value = min_tree.value # Remove min tree from queue self.trees.remove(min_tree) # Children become new binomial queue children_queue = list(reversed(min_tree.children)) # Merge the two queues self._merge_queue(children_queue) return min_value def size(self): """Return number of elements - O(log n)""" count = 0 for tree in self.trees: count += 2 ** tree.rank return count

Binomial Queue Visualization