TD 8 - Binomial Heaps¶

0. Preliminaries¶

We start here by defining a class BH of binomial heaps. Binomial heaps being a heap of binary trees, a class BT of binary trees is also defined.

All functions produced in the exercise are enlisted within the class definition but repeated later on the fly.

A few properties of a BT¶

By design, the number of nodes in binomial tree $B_k$ is $|B_0|=1$, $|B_1|=2\times |B_0|=2$ and so forth, so that $$|B_k|=2^k.$$
The depth of $B_k$ is one more than that of $B_{k-1}$ with depth of $B_0$ being $0$, so that $B_k$ has depth $k$
By construction, the number of nodes $n_{k,i}$ of $B_k$ at level $i$ satisfies $$ n_{k,i}=n_{k-1,i-1}+n_{k-1,i-1} $$ with $n_{k,0}=1$ and $n_{k,k+1}=0$. It can be checked by recursion proof that this implies $$n_{k,i}=C_k^i=\left(\begin{smallmatrix}k \\ i \end{smallmatrix} \right).$$
Still as an elementary consequence of construction, the $i$-th child (reading from the right) of $B_k$ is the root of $B_i$.

As a consequence of these properties, $B_k$ has depth $k$ and size $2^k$, so letting $n=2^k$, $B_k$ has $\log n$ depth. Besides, since $B_k$ has up $k$ children, for $n=2^k$, $B_k$ has no more than $\log n$ children: by construction, this holds true for every subtree of $B_k$ (being itself a $B_{k'}$ for some $k'<k$).

import numpy as np
import sys

class BH: # binomial heap
    def __init__(self,elements=[]):
        self.trees = []
        for e in elements:
            self.insert(e)
            
    def insert(self,e):
        if len(self.trees) == 0:
            self.trees = [BT(e)]
        else:
            self.fuse(BH([e]))
            
    def fuse(self,bh): # fuse in another BH
        union_trees = self.trees + bh.trees
        union_trees.sort(key=lambda x : x.size)                 # sort the trees by size

        tree_pairs=[ [j,j+1] for j in range(len(union_trees))]  # sliding window of all pairs (j,j+1) to compare trees pairwise

        i=0
        while i < len(tree_pairs)-1:

            if union_trees[tree_pairs[i][0]].size == union_trees[tree_pairs[i][1]].size:
                union_trees[tree_pairs[i][0]]=union_trees[tree_pairs[i][0]].fuse(union_trees[tree_pairs[i][1]])   # fusing trees of equal size
                union_trees[tree_pairs[i][0]].size *= 2
                union_trees.pop(tree_pairs[i][1])   # one tree is gone, reducing union_trees length
                tree_pairs.pop(-1)
            else:  # trees are of different size: move to next pair
                i+=1            
        self.trees = union_trees   
        
    def minimum(self):
        return min([t.value for t in self.trees])     
    
    def remove_minimum(self):
        min_value = self.minimum()
        for index,t in enumerate(self.trees):
            if t.value == min_value:
                del self.trees[index]

                bh = BH()
                bh.trees = t.children
                self.fuse(bh)            

    def find_element(self,value):
        for t in self.trees:
            foundVal,path=t.find_element(value)
            if foundVal:
                return path
        return []
    
    def reduce_value(self,value,delta):
        path = self.find_element(value)
        path[-1].value -= delta
        new_value = path[-1].value
        i=1
        while i<len(path) and path[-1-i].value>path[-1-i+1].value:
            path[-1-i+1].value = path[-1-i].value
            path[-1-i].value = new_value
            i+=1
    
    def remove_element(self,value):
        self.reduce_value(value,value+sys.maxsize//2)
        self.remove_minimum()
    
    def print_heap(self):
        for index,t in enumerate(self.trees):
            print("BTree",index)
            t.print_tree()
            print("\n")  
        return

class BT: # binomial tree
    def __init__(self,value): #,children=[],size=1):
        self.value = value
        self.size = 1
        self.children = [] #children
        
    def fuse(self,bt):
        if self.value < bt.value:
            self.children.insert(0,bt)
            return self
        else:
            bt.children.insert(0,self)
            return bt
        
        self.size += bt.size
    
    def find_element(self,value):        
        if self.value == value:
            return True,[self]
        else:
            foundVal = False
            i=0
            while (not foundVal and i<len(self.children) and self.value<value):
                foundVal,path=self.children[i].find_element(value)                    
                i+=1

            if foundVal:
                return True,[self]+path

            return False,[]

        
    def print_tree(self,level=0):
        print(" |---" * level,self.value)        
        for child in self.children:
            if child == None:
                print(" |---" * (level+1),"*")
            else:
                child.print_tree(level+1)

treeSize = 20
elements = np.random.randint(0,100,treeSize)

mybh=BH(elements)

mybh.print_heap()

print("Removing minimum, i.e.,",mybh.minimum(),":\n")

mybh.remove_minimum()

mybh.print_heap()

BTree 0
 0
 |--- 13
 |--- |--- 26
 |--- 55


BTree 1
 2
 |--- 4
 |--- |--- 7
 |--- |--- |--- 53
 |--- |--- |--- |--- 54
 |--- |--- |--- 38
 |--- |--- 55
 |--- |--- |--- 60
 |--- |--- 92
 |--- 21
 |--- |--- 45
 |--- |--- |--- 77
 |--- |--- 48
 |--- 36
 |--- |--- 75
 |--- 74


Removing minimum, i.e., 0 :

BTree 0
 55


BTree 1
 13
 |--- 26


BTree 2
 2
 |--- 4
 |--- |--- 7
 |--- |--- |--- 53
 |--- |--- |--- |--- 54
 |--- |--- |--- 38
 |--- |--- 55
 |--- |--- |--- 60
 |--- |--- 92
 |--- 21
 |--- |--- 45
 |--- |--- |--- 77
 |--- |--- 48
 |--- 36
 |--- |--- 75
 |--- 74

1. Looking for minimum in a binomial heap¶

Since BH's are a stack of BT's which are "min-sorted", the minimum in a BH is one of the roots of its BT's, so no more than $\log n$ of them. Hence a complexity of $O(\log n)$ to find the minimum in a BH.

Function: minimum INPUT: self of BH class OUTPUT: the minimum element of self

# At BH level

def minimum(self):
    return min([t.value for t in self.trees])     

mybh.minimum()

2

2. Fusing two binomial heaps (BH)¶

The union of two BHs is in general not a BH as no two BTs of the same size can be found in a BH: by the union operation, two BTs of the same size could be found.

The idea in the fusion of two BTs is to ensure that no two trees in the heaps are of the same size. If it's the case, the trees are fused (in a tree twice as large), and so on over all trees (one must be careful that the newly created tree could be of the same size as other trees). Specifically the algorithm runs as follows:

first create a list of all their BTs in growing size order.
iterate in the list and, when two BTs of the same size are met, fuse them into a BT of next order size.
continue to iterate until the end of the list. Be careful that the newly fused BTs can be of the same size as the already existing next BT in the list. The cost of the method is at most $O(\log n)$ for two BHs of sizes of order $n$, since no more than $O(\log n)$ BTs are found in a BH of size $n$.

This result is then used to add up a new node to a BH: by merging the current BH with the BH with the new node as singleton tree node.

Function: fuse INPUT: self of BH class, bh of BH class OUTPUT: the fusion of self and bh into self
Function: fuse INPUT: self of BT class, bt of BT class OUTPUT: the fusion of self and bh into self
Function: insert INPUT: self of BH class, element e OUTPUT: the update of self with element e inserted

# At BH level

def fuse(self,bh): # fuse in another BH
    union_trees = self.trees + bh.trees
    union_trees.sort(key=lambda x : x.size)                 # sort the trees by size

    tree_pairs=[ [j,j+1] for j in range(len(union_trees))]  # sliding window of all pairs (j,j+1) to compare trees pairwise

    i=0
    while i < len(tree_pairs)-1:

        if union_trees[tree_pairs[i][0]].size == union_trees[tree_pairs[i][1]].size:
            union_trees[tree_pairs[i][0]]=union_trees[tree_pairs[i][0]].fuse(union_trees[tree_pairs[i][1]])   # fusing trees of equal size
            union_trees[tree_pairs[i][0]].size *= 2
            union_trees.pop(tree_pairs[i][1])   # one tree is gone, reduncing union_trees length
            tree_pairs.pop(-1)
        else:  # trees are of different size: move to next pair
            i+=1            
    self.trees = union_trees  
    
    
# At BT level

def fuse(self,bt):
    if self.value < bt.value:
        self.children.insert(0,bt)
        return self
    else:
        bt.children.insert(0,self)
        return bt

    self.size += bt.size
    
# At BH level: insert a new node
def insert(self,e):
    if len(self.trees) == 0:
        self.trees = [BT(e)]
    else:
        self.fuse(BH([e]))

3. Removing the smallest element¶

To remove the smallest element of a BH, it suffices to find this smallest element (through the function minimum()), which needs to be the root of a BT of the heap, then break the corresponding tree into its children and fuse them back with the original heap.

The complexity of minimum() is $O(\log n)$. The fusion of the children into the BH both come at cost $O(\log n)$. The total resulting complexity is then $$O(\log n)$$

Function: remove_minimum INPUT: self of BH class OUTPUT: the updated BH with minimum element removed

# At BH level

def remove_minimum(self):
    min_value = self.minimum()
    for index,t in enumerate(self.trees):
        if t.value == min_value:
            del self.trees[index]

            bh = BH()
            bh.trees = t.children
            self.fuse(bh)

treeSize = 20
elements = np.random.randint(0,100,treeSize)

mybh=BH(elements)

print("Original BH:\n")
mybh.print_heap()

mybh.remove_minimum()

print("After removal of smallest element:\n")
mybh.print_heap()

Original BH:

BTree 0
 4
 |--- 31
 |--- |--- 34
 |--- 53


BTree 1
 2
 |--- 4
 |--- |--- 8
 |--- |--- |--- 65
 |--- |--- |--- |--- 88
 |--- |--- |--- 70
 |--- |--- 41
 |--- |--- |--- 97
 |--- |--- 23
 |--- 25
 |--- |--- 28
 |--- |--- |--- 48
 |--- |--- 53
 |--- 42
 |--- |--- 46
 |--- 30


After removal of smallest element:

BTree 0
 30


BTree 1
 42
 |--- 46


BTree 2
 4
 |--- 4
 |--- |--- 25
 |--- |--- |--- 28
 |--- |--- |--- |--- 48
 |--- |--- |--- 53
 |--- |--- 31
 |--- |--- |--- 34
 |--- |--- 53
 |--- 8
 |--- |--- 65
 |--- |--- |--- 88
 |--- |--- 70
 |--- 41
 |--- |--- 97
 |--- 23

4. Find element in a heap and return path¶

To find an element in a heap, we must scan over all BTs and go down successively into each of them until the value met is larger than the sought for element (and of course, stop whenever the element is found). On the way, we can store the path to the found node as a list (or return [] if not found). By default, we will return the path to the first found element (no scan of further trees is done after the element is first found).

The complexity in the worst case is $\log n$ (number of BTs) times $\log n$ (depth of each BT), so $$O( (\log n)^2 )$$

Function: find_element INPUT: self of BH class, value OUTPUT: boolean of value found in BH , path to the value as a list
Function: find_element INPUT: self of BT class, value OUTPUT: boolean of value found in BH , path to the value as a list

# At BH level

def find_element(self,value):
    for t in self.trees:
        foundVal,path=t.find_element(value)
        if foundVal:
            return path
    return []  # default return if element not found


# At BT level, we return both the indicator on finding the node and the path to it

def find_element(self,value):        
    if self.value == value:
        return True,[self]
    else:
        foundVal = False
        i=0
        while (not foundVal and i<len(self.children) and self.value<value): # go down so long that self.value<value
            foundVal,path=self.children[i].find_element(value)                    
            i+=1

        if foundVal:
            return True,[self]+path  # create the path

        return False,[]

index = np.random.randint(0,len(elements))
a=mybh.find_element(elements[index])

print("Searching for value:",elements[index])

print("Path to value:",[a[i].value for i in range(len(a))])

Searching for value: 4
Path to value: [4]

5. Reducing the value of an element¶

Reducing an element consists in finding the element to be reduced (using the routine find_element) and then switch between the node and its parent so long that the parent has larger value than the node, up until reaching the root.

Function: reduce_value INPUT: self of BH class, value to be found and reduced, absolute value delta of the decrement of value (so to obtained value-delta) OUTPUT: None (updated self: operation performed in place)

# At BH level

def reduce_value(self,value,delta):
    path = self.find_element(value)
    path[-1].value -= delta
    new_value = path[-1].value
    i=1
    while i<len(path) and path[-1-i].value>path[-1-i+1].value:
        path[-1-i+1].value = path[-1-i].value
        path[-1-i].value = new_value
        i+=1

treeSize = 20
elements = np.random.randint(0,100,treeSize)

mybh=BH(elements)

print("Original BH:\n")
mybh.print_heap()

delta=10
index = np.random.randint(0,len(elements))
mybh.reduce_value(elements[index],delta)

print("Reducing",elements[index],"by",delta,":\n")
mybh.print_heap()

Original BH:

BTree 0
 40
 |--- 82
 |--- |--- 94
 |--- 85


BTree 1
 1
 |--- 1
 |--- |--- 46
 |--- |--- |--- 93
 |--- |--- |--- |--- 95
 |--- |--- |--- 51
 |--- |--- 84
 |--- |--- |--- 93
 |--- |--- 5
 |--- 37
 |--- |--- 56
 |--- |--- |--- 83
 |--- |--- 83
 |--- 47
 |--- |--- 61
 |--- 57


Reducing 83 by 10 :

BTree 0
 40
 |--- 82
 |--- |--- 94
 |--- 85


BTree 1
 1
 |--- 1
 |--- |--- 46
 |--- |--- |--- 93
 |--- |--- |--- |--- 95
 |--- |--- |--- 51
 |--- |--- 84
 |--- |--- |--- 93
 |--- |--- 5
 |--- 37
 |--- |--- 56
 |--- |--- |--- 73
 |--- |--- 83
 |--- 47
 |--- |--- 61
 |--- 57

6. Removing an element from the heap¶

To remove an element from the heap, a fun "trick" is used:

find the element to remove from the heap,
affect it value $-\infty$ and restore the binomial heap property (so to get the node back at the root of the tree),
remove the minimum!

Again, the complexity is equivalent to the complexity of 1. + 2. + 3., all in $O(\log n)$, so a total complexity of $O(\log n)$.

Function: remove_element INPUT: self of BH class, value to remove OUTPUT: None (self with value remove, operation in place)

# At BH level

def remove_element(self,value):
    self.reduce_value(value,value+sys.maxsize//2) ## division by 2 to avoid calculus overflow
    self.remove_minimum()

treeSize = 20
elements = np.random.randint(0,100,treeSize)

mybh=BH(elements)

print("Original BH\n")
mybh.print_heap()

index = np.random.randint(0,len(elements))
mybh.remove_element(elements[index])

print("After removal of",elements[index],"\n")
mybh.print_heap()

Original BH

BTree 0
 2
 |--- 53
 |--- |--- 74
 |--- 37


BTree 1
 0
 |--- 13
 |--- |--- 32
 |--- |--- |--- 76
 |--- |--- |--- |--- 79
 |--- |--- |--- 87
 |--- |--- 74
 |--- |--- |--- 81
 |--- |--- 64
 |--- 33
 |--- |--- 79
 |--- |--- |--- 97
 |--- |--- 60
 |--- 52
 |--- |--- 55
 |--- 99


After removal of 0 

BTree 0
 99


BTree 1
 52
 |--- 55


BTree 2
 2
 |--- 13
 |--- |--- 32
 |--- |--- |--- 76
 |--- |--- |--- |--- 79
 |--- |--- |--- 87
 |--- |--- 74
 |--- |--- |--- 81
 |--- |--- 64
 |--- 33
 |--- |--- 79
 |--- |--- |--- 97
 |--- |--- 60
 |--- 53
 |--- |--- 74
 |--- 37