Editing 2–3 heap (section)

== Polynomial of trees ==
Source:<ref name=":0">{{Cite journal|last=Takaoka|first=Tadao|date=March 2003 |title=Theory of 2–3 Heaps |journal=Discrete Applied Mathematics|language=en|volume=126|issue=1 |pages=115–128|doi=10.1016/S0166-218X(02)00219-6|doi-access=free}}</ref> 

A linear tree of size <math>r</math> is a sequential path of <math>r</math> nodes with the first node as a root of the tree and it is represented by a bold <math>\mathbf{r}</math> (e.g. <math>\mathbf{1}</math> is a linear tree of a single node). Product <math>P = ST</math> of two trees <math>S</math> and <math>T</math>, is a tree produced by replacing every node of <math>S</math> by a copy of <math>T</math>; for each edge of <math>S</math>, there is an edge in <math>ST</math> connecting the roots of the trees that replaced the endpoints of the edge. This definition of product is associative but not commutative. The sum <math>S+T</math> of two trees <math>S</math> and <math>T</math> is the [[Tree_(graph_theory)#Forest|forest]] of the two trees <math>S</math> and <math>T</math>.

The operation <math>\triangleleft</math> on trees <math>S,T</math> is defined as follows.  The tree <math>L = S \triangleleft T</math> is produced by linking the root of the tree <math>T</math> as a child of the root of tree <math>S</math>. Now consider the linear tree <math>\mathbf{r}</math>. The tree <math>\mathbf{r}^{i}</math> is defined by combining r copies of <math>\mathbf{r}^{i-1}</math> as follows:

<math>\mathbf{r}^i = \mathbf{r}^{i - 1} \triangleleft \mathbf{r}^{i - 1} \triangleleft \dots \triangleleft \mathbf{r}^{i - 1}</math> (evaluated right to left).

The path created from this linking forms the <math>i</math>th trunk of <math>\mathbf{r}^{i}</math> which can also be called the <math>i</math>th dimension of the tree.

An r-ary polynomial of trees is defined as <math>P = \mathbf{a}_{k-1}\mathbf{r}^{k-1} + \dots + \mathbf{a}_1\mathbf{r} + \mathbf{a}_0</math> where <math>0 \leq a_i \leq r-1</math>. This polynomial notation for trees of <math>n</math> nodes is unique. The tree <math>\mathbf{a}_i\mathbf{r}^i</math> consists of <math>a_i</math> copies of <math>\mathbf{r}^i</math> such that their roots are connected with <math>a_i-1</math> edges sequentially. The path of these <math>a_i-1</math> edges is called the main trunk of the tree <math>\mathbf{a}_i\mathbf{r}^i</math>. Furthermore, an r-ary polynomial of trees is called an r-nomial queue if nodes of the polynomial of trees are associated with keys satisfying the [[heap property]]. 
[[File:2 3 heaps dim.svg|thumb|A polynomial heap, in fact a (2,3) heap with a dimension representation of its trees]]
=== Operations on r-nomial queues ===
To '''merge''' two terms of form <math>\mathbf{a}_i \mathbf{r}^i</math> and <math>\mathbf{a}'_i \mathbf{r}^i</math>, the trees are reordered in the main trunk based on the keys in the root of trees. If <math>a_i + a'_i \geq r</math> there will be a term of form <math>(\mathbf{a}_i+\mathbf{a}'_i-\mathbf{r}) \mathbf{r}^i</math> and a carry tree <math>\mathbf{r}^{i+1}</math>. Otherwise, there is only a tree <math>(\mathbf{a}_i+\mathbf{a}'_i) \mathbf{r}^i</math>. The sum of two r-nomial queues are similar to the addition of two number in base <math>r</math>.

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 <math>O(r \log_r{n})</math> time.

A '''delete''' operation of the minimum is done by finding the minimum in the root of a tree, say <math>T</math> and deleting it. The resulting polynomial queue <math>Q</math> is added back to <math>P-T</math> in total time <math>O(r \log_r{n})</math>.