# Binomial Queue

## Character

for $$B_k$$

• has exactly $$2^k$$ nodes
• the number of nodes at depth $$d$$ is $$\binom{k}{d}$$

for a priority queue of size $$13$$

• $$13 = 2^0 + 0\times 2^1 + 2^2 + 2^3 = 1101_2$$

A binomial queue of $$N$$ elements can be built by $$N$$ sccessive insertions in $$O(N)$$ time.

## Operation

### FindMin

There are at most $$\lceil \log{N}\rceil$$ roots, hence $$T_p = O(\log{N})$$

### Merge

$$T_p = O(\log{N})$$

### DeleteMin

$$T_p=O(\log{N})$$

### Decreased Key

$$T_p=O(\log{N})$$