Skip to main content

FibonacciHeap

data-structure-typed

data-structure-typed / FibonacciHeap

Class: FibonacciHeap<E>

Defined in: data-structures/heap/heap.ts:1286

Fibonacci heap (min-heap) optimized for fast merges and amortized operations.

Remarks​

Time O(1), Space O(1)

Example​

examples will be generated by unit test

Type Parameters​

E​

E

Constructors​

Constructor​

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

Defined in: data-structures/heap/heap.ts:1294

Create a FibonacciHeap.

Parameters​

comparator?​

Comparator<E>

Comparator to order elements (min-heap by default).

Returns​

FibonacciHeap<E>

New FibonacciHeap instance.

Remarks​

Time O(1), Space O(1)

Accessors​

min​

Get Signature​

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

Defined in: data-structures/heap/heap.ts:1325

Get the current minimum node.

Remarks​

Time O(1), Space O(1)

Returns​

FibonacciHeapNode<E> | undefined

Min node or undefined.

root​

Get Signature​

get root(): FibonacciHeapNode<E> | undefined;

Defined in: data-structures/heap/heap.ts:1308

Get the circular root list head.

Remarks​

Time O(1), Space O(1)

Returns​

FibonacciHeapNode<E> | undefined

Root node or undefined.

Methods​

consumeLinkedList()​

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

Defined in: data-structures/heap/heap.ts:1374

Collect nodes from a circular doubly linked list starting at head.

Parameters​

FibonacciHeapNode<E>

Start node of the circular list.

Returns​

FibonacciHeapNode<E>[]

Array of nodes from the list.

Remarks​

Time O(K), Space O(K)

merge()​

merge(heapToMerge): void;

Defined in: data-structures/heap/heap.ts:1445

Meld another heap into this heap.

Parameters​

heapToMerge​

FibonacciHeap<E>

Another FibonacciHeap to meld into this one.

Returns​

void

void

Remarks​

Time O(1), Space O(1)

mergeWithChild()​

mergeWithChild(parent, node): void;

Defined in: data-structures/heap/heap.ts:1396

Insert a node into a parent's child list (circular).

Parameters​

parent​

FibonacciHeapNode<E>

Parent node.

node​

FibonacciHeapNode<E>

Child node to insert.

Returns​

void

void

Remarks​

Time O(1), Space O(1)

pop()​

pop(): E | undefined;

Defined in: data-structures/heap/heap.ts:1416

Remove and return the minimum element, consolidating the root list.

Returns​

E | undefined

Minimum element or undefined.

Remarks​

Time O(log N) amortized, Space O(1)

push()​

push(element): this;

Defined in: data-structures/heap/heap.ts:1353

Push an element into the root list.

Parameters​

element​

E

Element to insert.

Returns​

this

This heap.

Remarks​

Time O(1) amortized, Space O(1)