2–3 heap

In computer science, a 2–3 heap is a data structure, a variation on the heap, designed by Tadao Takaoka in 1999.

The structure is similar to the Fibonacci heap, and borrows from the 2–3 tree.

Time costs for some common heap operations are: Source:[1] A linear tree of size

we connect the roots of the trees corresponding to the endpoints of the edge.

Note that this definition of product is associative but not commutative.

edges is called the main trunk of the tree

Furthermore, an r-ary polynomial of trees is called an r-nomial queue if nodes of the polynomial of trees are associated with keys in heap property.

The sum of two r-nomial queues are similar to the addition of two number in base

An insertion of a key into a polynomial queue is like merging a single node with the label of the key into the existing r-nomial queue, taking

is formed by linking roots of 2 or 3 trees of dimension

When keys are assigned to the nodes of an extended polynomial of trees in heap order it is called an

is the local neighborhood, defined for nodes not on the main trunks of trees in the heap.

in the extended polynomial, there might be a need to adjust for the carry on trees that can occur from the insertion.

Delete-min: First find the minimum by scanning the roots of the trees.

to make sure only the minimum node was removed from the heap.

(The merging operation is done through multiple insertions, each taking at most 3 comparisons).

For the case in which the workspace is of size 4, remove

th trunk of length two (three nodes in a line) but causes a loss of an

This loss is fixed by moving around trees from workspace of nodes on the

This process continues upwards in dimension until it is resolved.

was at the top level of its tree, then the heap property was not violated from decrease key and no tree removal is required.

The actual cost will be the number of comparisons performed during the operation.

Decrease Key The number of nodes on trunks can increase or decrease during the removal of a tree, depending on the size of the workspace.

The change in potential and number of comparisons can be observed in each case, which allows for a computation of the amortized cost.

, no comparisons are needed because of the heap property and

increases by 1, which gives an amortized cost of 0.

The fixing process ends in one of the earlier cases or if no higher trunk exists.

Therefore the amortized cost is 0 throughout the initial insertion and the carry overs.

due to the carry overs and constant number of comparisons each time.

insertions are done which take a constant amortized time each.