[+] Priority Queue: Mergeable Heap
A mergeable heap is a heap with the support of operations union.
Consider the max/min heap, if we want to merge two heaps of size \(n, m\), it will take \(O(n+m)\) using build_heap. However, there is another implementation which max takes \(O(\lg n)\) while union takes \(O(\lg(n+m))\).
Binomial Tree
A binomial tree is constructed from structural induction. - \(B_0\): the base case with one node - \(B_k\): two copies of \(B_{k-1}\), connecting the roots with an edge, and let the root of the one of the \(B_{k-1}\) be the root of \(B_k\).
Claim 1 The number of \(B_k\) is \(n = 2^k\)
Claim 2 The height of \(B_k\) is \(h = k\)
proof. By induction, \(h_0 = 0\), assume \(h_{k-1} = k-1\), then note that \(B_k\) add one more edge from root to the root of \(B_{k-1}\) so that \(h_k = k\).
Claim 3 The root of \(B_k\) has subtrees \(B_0,..., B_{k-1}\).
proof. By construction, the left most subtree of the root is \(B_{k-1}\). Then, the rest is a \(B_{k-1}\), which by induction hypothesis, has subtrees \(B_0, ..., B_{k-2}\).
Claim 4 For level \(k\) of a \(h\) height binomial tree, the number of nodes at level \(k\) is \(h\choose k\).
proof. Since a tree of height \(h\) has subtrees \(B_0, ..., B_{h-1}\). For each of the tree, the number of nodes at level \(k-1\) is \({m-1\choose k-1}, m = k-1,...,h-1\). Summing them together we have that
Binomial Forest
A binomial forest is a set of distinct size binomial trees.
Since each decimal number has a unique binary representation, for \(n\) nodes, we have a unique binomial forest \(F_{n}\).
For example, \(13 = b'1101\), so that the binomial forest is \(F_{13} =\{B_0, B_2, B_3\}\)
Claim 5 Let \(k\) be the number of binomial trees in the forest, \(k = |F_n| \leq \lceil \lg (n + 1)\rceil\).
proof. \(k\) is smaller than the number of digits in binary representation.
Mergeable Min Heap
Object
A binomial forest \(F_n\), for each tree in the forest, for each node in the tree, the key is greater than its children.
union
Let \(H_1, H_2\) be two mergable heap of size \(n_1, n_2\). union will merge trees with the same size, by simplying compare the root, where the smaller one becomes the new root.
Correctness
Merging trees is equivalent to bitwise add \(n_1 + n_2\), thus the resulting forest is still a binomial forest. For each tree in the new forest. If it merges with some other trees, then the new root is smaller of equal to its original children, and by the comparison, is also smaller than or equal to its new child from the other tree.
Runtime
Each tree-wise merge takes constant time, the number of tree merge equals the max bits in bit-wise add. Thus the time is \(O(\lg(\max(n_1, n_2))) \in O(\lg(n_1 + n_2))\)
min, extract_min, insert
min will simply return the minimum of roots of all trees in the forest.
Taking \(O(\lg n)\) time since there are at most \(\lg (n+1)\) trees.
extract_min will remove the minimum root, by claim 3, that tree will be broken into a forest. Thus, merge the two new forest.
Taking \(O(\lg n)\) time since the two forests two merge is at most size \(\lg(n)-1, \lg(n)\).
insert merge the forest with a new forst of \(F_1 = \{B_1\}\). Taking \(O(\lg n)\) time.
Implementation
Implementation code
from math import inf
from matplotlib.pyplot import plot
from .priority_queue import PriorityQueue
from .plot_trees import TreeNode, construct_tree_nodes, plot_tree
class Node:
def __init__(self, k):
self.k = k
self.children = []
@property
def degree(self):
return len(self.children)
def add(self, other):
if self.degree != other.degree:
raise ValueError("Cannot merge binomial trees of different size")
self.children.insert(0, other)
class MergableHeap(PriorityQueue):
def __init__(self, arr=[], ascending=False):
self.trees = dict()
self.bit = -1
self.ascending = ascending
if ascending:
self.compare = lambda x, y: x < y
else:
self.compare = lambda x, y: x > y
for x in arr:
self.insert(x)
def from_trees(self, trees):
for tree in trees:
self.trees[tree.degree] = tree
if tree.degree > self.bit:
self.bit = tree.degree
def __peek_node(self):
m, trees_k = inf, -1
for i, node in self.trees.items():
if self.compare(node.k, m):
m = node.k
trees_k = i
return self.trees[trees_k]
def peek(self):
return self.__peek_node().k
def union(self, other):
if self.ascending != other.ascending:
raise ValueError("Two Mergable Heaps have different order")
if other.bit == -1:
return
if self.bit == -1:
self.trees = other.trees
self.bit = other.bit
return
bit, max_bit = 0, max(self.bit, other.bit)
new_trees = dict()
reg = []
while bit <= max_bit:
if self.trees.get(bit):
reg.append(self.trees[bit])
if other.trees.get(bit):
reg.append(other.trees[bit])
if len(reg) == 1:
new_trees[bit] = reg.pop()
elif len(reg) == 2:
t1 = reg.pop()
t2 = reg.pop()
if self.compare(t1.k, t2.k):
t1.add(t2)
reg.append(t1)
else:
t2.add(t1)
reg.append(t2)
elif len(reg) == 3:
new_trees[bit] = reg.pop()
t1 = reg.pop()
t2 = reg.pop()
if self.compare(t1.k, t2.k):
t1.add(t2)
reg.append(t1)
else:
t2.add(t1)
reg.append(t2)
bit += 1
if len(reg) == 1:
new_trees[bit] = reg.pop()
else:
bit -= 1
self.trees = new_trees
self.bit = bit
def insert(self, k):
if len(self.trees) == 0:
self.trees[0] = Node(k)
self.bit = 0
else:
new_mh = MergableHeap([k], ascending=self.ascending)
self.union(new_mh)
def pull(self):
m = self.__peek_node()
del self.trees[m.degree]
other = MergableHeap(ascending=self.ascending)
other.from_trees(m.children)
self.union(other)
return m.k
def plot(self, path):
forest_root = TreeNode("")
for tree in self.trees.values():
forest_root.children.append(construct_tree_nodes(tree, label_fn=lambda x: x.k, children_attr ="children"))
return plot_tree(forest_root, path)
from assets.mergeable_heap import MergableHeap
arr1 = [3, 2, 4]
mq1 = MergableHeap(arr1, ascending=True)
mq1.plot("./assets/mq_1.jpg")
arr2 = [6, 1, 8, 5, 9, 7, 10]
mq2 = MergableHeap(arr2, ascending=True)
mq2.plot("./assets/mq_2.jpg")
