Function
| Static Public Summary | ||
| public |
* cascading_cut(y: *) |
|
| public |
consolidate(compare: *, l: *): * CONSOLIDATE: Consolidate the root list of a heap. |
|
| public |
cut(x: *, y: *) |
|
| public |
link(y: *, x: *) FIB-HEAP-LINK |
|
| public |
list_reset_parent(children: *) |
|
Static Public
public * cascading_cut(y: *) source
import cascading_cut from '@heap-data-structure/fibonacci-heap/src/cascading_cut.js'Params:
| Name | Type | Attribute | Description |
| y | * |
public consolidate(compare: *, l: *): * source
import consolidate from '@heap-data-structure/fibonacci-heap/src/consolidate.js'CONSOLIDATE: Consolidate the root list of a heap.
The next step, in which we reduce the number of trees in the Fibonacci heap, is consolidating the root list of H, which the call CONSOLIDATE(H) accomplishes. Consolidating the root list consists of repeatedly executing the following steps until every root in the root list has a distinct degree value:
Find two roots x and y in the root list with the same degree. Without loss of generality, let x.key <= y.key.
Link y to x: remove y from the root list, and make y a child of x by calling the FIB-HEAP-LINK procedure. This procedure increments the attribute x:degree and clears the mark on y.
The procedure CONSOLIDATE uses an auxiliary array A[0..D(H.n)] to keep track of roots according to their degrees. If A[i] = y, then y is currently a root with y.degree = i. Of course, in order to allocate the array we have to know how to calculate the upper bound D(H.n) on the maximum degree, but we will see how to do so in Section 19.4.
Params:
| Name | Type | Attribute | Description |
| compare | * | Comparison function. |
|
| l | * | Root list. |
Return:
| * |
public cut(x: *, y: *) source
import cut from '@heap-data-structure/fibonacci-heap/src/cut.js'Params:
| Name | Type | Attribute | Description |
| x | * | ||
| y | * |
public link(y: *, x: *) source
import link from '@heap-data-structure/fibonacci-heap/src/link.js'FIB-HEAP-LINK
Precondition: y is in the root list of some heap.
Params:
| Name | Type | Attribute | Description |
| y | * | ||
| x | * |
public list_reset_parent(children: *) source
import list_reset_parent from '@heap-data-structure/fibonacci-heap/src/list_reset_parent.js'Params:
| Name | Type | Attribute | Description |
| children | * |