Overview

Time Complexities

Strict Fibonacci Heap (Brodal, Lagogiannis & Tarjan, 2012) is the first heap structure that uses pointer-based heap implementation to match the time complexities of Fibonacci Heap in the worst case, as shown in the chart below:

Basic Structure

• Single heap-ordered tree with N nodes

• Self-adjusting through transformations to keep the tree in the desirable structure

• Minimum at the root (e.g. children nodes are always bigger than their parents)

• A node can be either an Active/White node or a Passive/Red node

• All nodes have O(logN) degree

• Root is always Passive/Red

• A node's Active/White children are to the left of its Passive/Red

  children

• Space Complexity: O(N)