DSAverse

Heap-like Data Structures

Loading Heap Structures...

Max Heap

root: 90

Binomial Queue

A forest of binomial trees with unique ranks. Merging two queues mirrors binary number addition — carry a tree when two of the same rank collide.

Queue Visualization

Speed

Empty queue — insert values to begin

Trees

Total Nodes

—

Ranks

Insert values to build the binomial queue, then try Extract Min.

Complexity

O(1)*

Insert

O(log n)

Extract Min

O(log n)

Find Min

O(log n)

Merge

* amortized

Binomial Tree B_k

•B₀ is a single node; B_k = two B_k-1 trees linked together
•Exactly 2^k nodes and height k
•Root has k children: B_k-1, B_k-2, …, B₀
•Min-heap property: every parent ≤ its children

Binary Addition Analogy

•Each rank is a bit position — at most one tree per rank
•Two B_k trees merge into B_k+1 — a carry
•Insert = adding 1 in binary to the node count

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

Active Recall Quiz

Question 1 of 3

Merging two binomial queues is analogous to which mathematical operation?

DSAverse

Heap-like Data Structures

Loading Heap Structures...

Max Heap

root: 90

DSAverse

DSAverse

Binomial Queue

Queue Visualization

Complexity

Binomial Tree Bk

Binary Addition Analogy

Active Recall Quiz

DSAverse

Binomial Queue

Queue Visualization

Complexity

Binomial Tree Bk

Binary Addition Analogy

Active Recall Quiz

Binomial Tree B_k

Binomial Tree B_k