2–3 heap explained

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:

Delete-min takes

O(log(n))

amortized time.

Decrease-key takes constant amortized time.
Insertion takes constant amortized time.

Polynomial of trees

Source:^[1]

A linear tree of size

is a sequential path of

nodes with the first node as a root of the tree and it is represented by a bold

(e.g.

is a linear tree of a single node). Product

P=ST

of two trees

and

, is a new tree with every node of

is replaced by a copy of

and for each edge of

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. Sum

S+T

of two trees

and

is the collection of two trees

and

An r-ary polynomial of trees is defined as

P=a_k-1r^k-1+...+a_1r+a₀

where

0\leqa_i\leqr-1

. This polynomial notation for trees of

nodes is unique. The tree

	i
a
	ir

is actually

a_i

copy of

rⁱ

that their roots are connected with

a_i-1

edges sequentially and the path of these

a_i-1

edge is called the main trunk of the tree

	i
a
	ir

. 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.

Operations on r-nomial queues

To merge two terms of form

a_irⁱ

and

a'_irⁱ

, we just reorder the trees in the main trunk based on the keys in the root of trees. If

a_i+a'_i\geqr

we will have a term of form

(a_i+a'_i-r)rⁱ

and a carry tree

rⁱ⁺¹

. Otherwise, we would have only a tree

(a_i+a'_i)rⁱ

. So the sum of two r-nomial queues are actually 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

O(rlog_r{n})

time.

To delete the minimum, first, we need to find the minimum in the root of a tree, say

, then we delete the minimum from

and we add the resulting polynomial queue

P-T

in total time

O(rlog_r{n})

(2,3)-heap

Source:

(l,r)-

tree

T(i)

is defined recursively by

T(i)=T_1(i-1)\triangleleft...\triangleleftT_s(i-1)

for

i\geq1

(

is between

and

(s-1)

\triangleleft

operations are evaluated from right to left) where for two trees,

and

, the result of the operation

A\triangleleftB

is connecting the root of

as a rightmost child to the root of

and

T(0)

is a single node tree. Note that the root of the tree

T(i)

has degree

An extended polynomial of trees,

, is defined by

P=a_k-1T(k-1)+...+a_1T(1)+a₀

. If we assign keys into the nodes of an extended polynomial of trees in heap order it is called

(l,r)-heap

, and the special case of

l=2

and

r=3

is called

(2,3)-heap

Operations on (2,3)-heap

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

T(i)

be the tree containing minimum element and let

be the result of removing root from

T(i)

. Then merge

P-T(i)

and

(The merge operation is similar to merge of two r-nomial queues).

Insertion: In order to insert a new key, merge the currently existing (2,3)-heap with a single node tree,

T(0)

labeled with this key.

Decrease Key: To be done!

Notes and References

Takaoka. Tadao. March 2003 . Theory of 2–3 Heaps . Discrete Applied Mathematics. en. 126. 1 . 115–128. 10.1016/S0166-218X(02)00219-6. free.