Class FibonacciHeap<E>

Type Parameters

  • E

Constructors

constructor

Accessors

comparator min root size

Methods

_consolidate _defaultComparator _link add clear consumeLinkedList createNode merge mergeWithChild mergeWithRoot peek poll pop push removeFromRoot

Constructors

constructor

  • new FibonacciHeap<E>(comparator?): FibonacciHeap<E>

  • The constructor function initializes a FibonacciHeap object with an optional comparator function.

    Type Parameters

    • E

    Parameters

    • Optionalcomparator: Comparator<E>

      The comparator parameter is an optional argument that represents a function used to compare elements in the FibonacciHeap. If a comparator function is provided, it will be used to determine the order of elements in the heap. If no comparator function is provided, a default comparator function will be used.

    Returns FibonacciHeap<E>

Accessors

comparator

  • get comparator(): Comparator<E>

  • The function returns the comparator used for comparing elements.

    Returns Comparator<E>

    The _comparator property of the object.

min

  • get min(): undefined | FibonacciHeapNode<E>

  • The function returns the minimum node in a Fibonacci heap.

    Returns undefined | FibonacciHeapNode<E>

    The method is returning the minimum node of the Fibonacci heap, which is of type FibonacciHeapNode<E>. If there is no minimum node, it will return undefined.

root

size

  • get size(): number

  • The function returns the size of an object.

    Returns number

    The size of the object, which is a number.

Methods

Protected_consolidate

  • _consolidate(): void
  • Protected

    Time Complexity: O(n log n) Space Complexity: O(n)

    Remove and return the top element (the smallest or largest element) from the heap.

    Returns void

Protected_defaultComparator

  • _defaultComparator(a, b): number
  • Protected

    Default comparator function used by the heap.

    Parameters

    Returns number

Protected_link

add

  • add(element): FibonacciHeap<E>

  • Time Complexity: O(1) Space Complexity: O(1)

    Insert an element into the heap and maintain the heap properties.

    Parameters

    • element: E

    Returns FibonacciHeap<E>

    FibonacciHeap - The heap itself.

clear

  • clear(): void

  • Get the size (number of elements) of the heap.

    Returns void

    The size of the heap. Returns 0 if the heap is empty. Returns -1 if the heap is invalid.

ProtectedconsumeLinkedList

  • consumeLinkedList(head?): FibonacciHeapNode<E>[]
  • Protected

    Time Complexity: O(n), where n is the number of elements in the linked list. Space Complexity: O(1)

    Get the size (number of elements) of the heap.

    Parameters

    Returns FibonacciHeapNode<E>[]

    FibonacciHeapNode[] - An array containing the elements of the linked list.

ProtectedcreateNode

merge

  • merge(heapToMerge): void

  • Time Complexity: O(1) Space Complexity: O(1)

    merge two heaps. The heap that is merged will be cleared. The heap that is merged into will remain.

    Parameters

    Returns void

mergeWithChild

ProtectedmergeWithRoot

  • mergeWithRoot(node): void

  • Time Complexity: O(1) Space Complexity: O(1)

    Merge the given node with the root list.

    Parameters

    Returns void

Protectedpeek

  • peek(): undefined | E
  • Protected

    Time Complexity: O(1) Space Complexity: O(1)

    Peek at the top element of the heap without removing it.

    Returns undefined | E

    The top element or undefined if the heap is empty.

poll

  • poll(): undefined | E

  • Time Complexity: O(log n) Space Complexity: O(1)

    Remove and return the top element (the smallest or largest element) from the heap.

    Returns undefined | E

    The top element or undefined if the heap is empty.

pop

  • pop(): undefined | E

  • Time Complexity: O(log n) Space Complexity: O(1)

    Remove and return the top element (the smallest or largest element) from the heap.

    Returns undefined | E

    The top element or undefined if the heap is empty.

push

  • push(element): FibonacciHeap<E>

  • Time Complexity: O(1) Space Complexity: O(1)

    Insert an element into the heap and maintain the heap properties.

    Parameters

    • element: E

    Returns FibonacciHeap<E>

    FibonacciHeap - The heap itself.

ProtectedremoveFromRoot

  • removeFromRoot(node): void
  • Protected

    Time Complexity: O(1) Space Complexity: O(1)

    Remove and return the top element (the smallest or largest element) from the heap.

    Parameters

    Returns void

Settings

Member Visibility

On This Page

Constructors
Accessors
Methods