05: restricted containers #2

Priority Queues | Binomial Heaps | Fibonacci Heaps

binomial heaps

A heap based priority queue has efficient (O(lg(n))) insertion and remove the maximum, but cannot do efficient merge. Binomial heaps can solve this.
  • 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.
A binomial heap of size 13
BinomialQueueIntro

Joining of two equal-sized power-of-2 heaps

  1. Start:
    BinomialQueueJoinEqual
  2. Put the larger roots at the top with that root's left subtree as the right subtree of the other original root
    BinomialQueueJoinEqual
  3. Note: this isn't a max heap, this is a left heap ordered binomial tree with the largest element at the root

Joining of two binomial heaps (no carry)

  1. Start:
    BinomialQueueJoinNoCarry
  2. Join
    BinomialQueueJoinNoCarry

Joining of two binomial heaps (carry)

  1. Start:
    BinomialQueueJoinCarry
  2. Join Two 1-Heaps using "Equal Size Join" to create another 2-Heap
    BinomialQueueJoinCarry
  3. Join Two 2-Heaps using "Equal Size Join" to create another 4-Heap
    BinomialQueueJoinCarry
  4. Join Two 4-Heaps using "Equal Size Join" to create an 8-Heap
    BinomialQueueJoinCarry

Insertion of a new element into a binomial heap (this is joining of a sized 1 heap with the existing heap)

  1. Start:
    BinomialQueueInsert
  2. Join Two 1-Heaps using "Equal Size Join" to create another 2-Heap
    BinomialQueueInsert
  3. Join Two 2-Heaps using "Equal Size Join" to create another 4-Heap
    BinomialQueueInsert
  4. Join Two 4-Heaps using "Equal Size Join" to create an 8-Heap
    BinomialQueueInsert

Removal of a maximum in a power-of-2 heap

  1. Start:
    BinomialQueueRemoval
  2. Removal:
    BinomialQueueRemoval

Increase Key

  1. Start:
    BinomialQueueIncreaseKey
  2. Increase:
    BinomialQueueIncreaseKey
  3. Fixup:
    BinomialQueueIncreaseKey
  4. Fixup:
    BinomialQueueIncreaseKey

Decrease Key

  • Use fixdown

Delete Internal Element

  • Increase Key to beyond Maximum
  • Remove Maximum

Fibonacci Heaps

Fibonacci Heaps are Binomial Heaps with delayed merging.

Constant Time Insertion

  1. Start:
    FibonacciHeapInsert
  2. Insert One Element:
    FibonacciHeapInsert
  3. Insert One Element:
    FibonacciHeapInsert
  4. Insert One Element:
    FibonacciHeapInsert

Remove Max

  1. Start:
    FibonacciHeapRemoval
  2. Remove Max and Consolidate Two Single Nodes:
    FibonacciHeapRemoval
  3. Consolidate Two Double Nodes:
    FibonacciHeapRemoval
  4. Consolidate Two Quad Nodes:
    FibonacciHeapRemoval

Merge Heaps

  1. Simply Merge and Combine During Remove Max:
    FibonacciHeapMerge
  2. Fix Max:
    FibonacciHeapMerge

Increase Key

  1. Start:
    FibonacciHeapDecrease
  2. Increase 8 to 10, Cut Element and Mark Parent:
    FibonacciHeapDecrease
  3. Increase 7 to 26, Cut Element and Mark Parent:
    FibonacciHeapDecrease
  4. 20 is Marked, Do a Cascading Cut and Mark the Parent:
    FibonacciHeapDecrease
  5. Increase 15 to 40. Cut Children:
    FibonacciHeapDecrease
  6. 30 is marked, Do a Cascading Cut:
    FibonacciHeapDecrease

Priority Queue Time Complexities

  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

references

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