Binomial Heaps

Priority Queue Abstract Data Type

• Object: Set S of elements with “keys” (“priority”) that can be compared

• Operations: Insert(S,x), Max(S), Extract_Max(S)

What operation does Priority Queue ADT can’t do?

Union(Q1, Q2)

What data structure does ordinary priority Queue use?

Data type: Min-heap

Give min heap complecity for insert, min, extract min, union

• O(logn)

• O(1)

• O(logn)

  • N/A

Data structure of mergeable priority Queues

Min binomial heap

Min binomial heap runtime for insert, min, extract min, union

• O(logn)

• O(logn)

• O(logn)

  • O(logn)

Binomial trees vs Binomial Forest

• k is number of nodes to create 1 tree

  • k is n is number of total nodes for collection of distinct tress

How to create Bkth binary tree?

Take all the tress from {bk-1, …b1, b0} trees, attach a root node on top of them

Number of nodes per each depth of binomial tree

Binomial Coefficent (k choose choose depth)

Binary tree (Bk) properties

Binomial Forest Fn (size n)

Sequence of Bk trees with strictly decreasing k’ s and a total of n node

Binary Forest Properties

• n nodes

• n = <bt, bt-1, .. , b0> number of bits

  • has a(n) tress [# where bit is 1]

• edges = n - a(n)

Min Binomial Heap (size n)

• Each node in Fn stores one element

• Each bk in forest is min heap ordered (Min-Heap property)

Min-Heap property

• Parent is smaller than or equal to priority of children

  • Only valid for the whole path; not necessarily subtrees

Binomial Tree facts

• 1 key comparison for 1 binomial heap edge

• Binomial Heap for n elements can be built in O(n) key-comparisons; going in order of S

Explain these arrows. Why is it this way?

Green - left child pointer

Blue - right child pointer

red - parent pointer

Want atmost 3 pointers per node.

Where is head?

the root of B0

keys vs edges

Keys are stored valued in nodes

edges are connecting 2 nodes together in bk

Lemma 1 of binary tress

Can merge two min heap-ordered Bk trees into a single min heap-ordered Bk+1 tree with just one key comparison

Lemma 2 of binary trees

Deleting the root of a min heap-ordered Bk tree gives a min binomial heap

Explain what is going on in picture

When you add 2 binary heaps, you add each b0, b1, .., bk trees. The top shows carry and bottom is the new b0,…bk trees (which uses lemma 1 to combine root)

WC complexity of union(P,Q)

If each tree has atmost <= n nodes.
By fact and lemma 1 → we have atmost O(logn) trees each for p and q

Thus O(logn) key comparisons.