**Left Heap Ordered:**The key in each node of a binary tree is larger than or equal to all the keys in that node's left subtree**Power-of-2 Heap:**A left heap ordered tree consisting of a root node with an empty right subtree and a complete left subtree**Binomial Queue:**A set of power-of-2 heaps, no two of the same size.

- Start:

- Put the larger roots at the top with that root's left subtree as
the right subtree of the other original root

- Note: this isn't a max heap, this is a left heap ordered binomial tree with the largest element at the root

- Start:

- Join

- Start:

- Join Two 1-Heaps using "Equal Size Join" to create another 2-Heap

- Join Two 2-Heaps using "Equal Size Join" to create another 4-Heap

- Join Two 4-Heaps using "Equal Size Join" to create an 8-Heap

- Start:

- Join Two 1-Heaps using "Equal Size Join" to create another 2-Heap

- Join Two 2-Heaps using "Equal Size Join" to create another 4-Heap

- Join Two 4-Heaps using "Equal Size Join" to create an 8-Heap

- Start:

- Removal:

- Start:

- Increase:

- Fixup:

- Fixup:

- Use fixdown

- Increase Key to beyond Maximum
- Remove Maximum

- Start:

- Insert One Element:

- Insert One Element:

- Insert One Element:

- Start:

- Remove Max and Consolidate Two Single Nodes:

- Consolidate Two Double Nodes:

- Consolidate Two Quad Nodes:

- Simply Merge and Combine During Remove Max:

- Fix Max:

- Start:

- Increase 8 to 10, Cut Element and Mark Parent:

- Increase 7 to 26, Cut Element and Mark Parent:

- 20 is Marked, Do a Cascading Cut and Mark the Parent:

- Increase 15 to 40. Cut Children:

- 30 is marked, Do a Cascading Cut:

Double List | Binary Heap | Binomial Heap | Fibonacci Heap | |

insert | O(n) | O(lgn) | O(lgn) | O(1) |

highest | O(1) | O(1) | O(lgn) | O(1) |

delete highest | O(1) | O(lgn) | O(lgn) | O(lgn)* |

delete any | O(1) | O(lgn) | O(lgn) | O(lgn)* |

merge | O(n+m) | O(nlgm) | O(lg(n+m)) | O(1) |

sort | O(1) | O(nlgn) | O(nlgn) | O(nlgn) |

* amortized

- Adam Drozdek. "Data Structures and Algorithms in C++"
- Algorithms in C++, Parts 1-4: Robert Sedgewick. pages 383-387, 406-414
- Introduction to Algorithms: Cormen, Leiserson, Rivest and Stein. pages 410-411
- Introduction to Algorithms: Cormen, Leiserson, Rivest and Stein. pages 412-415